Leetcode/src/main/java/com/fishercoder/solutions/secondthousand/_1170.java at master · fishercoder1534/Leetcode · GitHub

Name: Leetcode/src/main/java/com/fishercoder/solutions/secondthousand/_1170.java at master · fishercoder1534/Leetcode · GitHub
Rating: 4.9 (4791 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
packagecom.fishercoder.solutions.secondthousand;

importjava.util.Arrays;

publicclass_1170 {
publicstaticclassSolution1 {
/*
 * Use simple iteration when finding counts
 * Time: O(n^m) where m is the size of queries and n is the size of words
 * Space: O(max(m, n) where m is the size of queries and n is the size of words)
 */
publicint[] numSmallerByFrequency(String[] queries, String[] words) {
int[] queriesMinFrequecies = newint[queries.length];
for (inti = 0; i < queries.length; i++) {
queriesMinFrequecies[i] = computeLowestFrequency(queries[i]);
 }

int[] wordsMinFrequecies = newint[words.length];
for (inti = 0; i < words.length; i++) {
wordsMinFrequecies[i] = computeLowestFrequency(words[i]);
 }
Arrays.sort(wordsMinFrequecies);

int[] result = newint[queries.length];
for (inti = 0; i < result.length; i++) {
result[i] = search(wordsMinFrequecies, queriesMinFrequecies[i]);
 }
returnresult;
 }

privateintsearch(int[] nums, inttarget) {
intcount = 0;
for (inti = nums.length - 1; i >= 0; i--) {
if (nums[i] > target) {
count++;
 } else {
break;
 }
 }
returncount;
 }

privateintcomputeLowestFrequency(Stringstring) {
char[] str = string.toCharArray();
Arrays.sort(str);
StringsortedString = newString(str);
intfrequency = 1;
for (inti = 1; i < sortedString.length(); i++) {
if (sortedString.charAt(i) == sortedString.charAt(0)) {
frequency++;
 } else {
break;
 }
 }
returnfrequency;
 }
 }

publicstaticclassSolution2 {
/*
 * Use binary search when finding counts
 * Time: O(n^logn) where m is the size of queries and n is the size of words
 * Space: O(max(m, n) where m is the size of queries and n is the size of words)
 */
publicint[] numSmallerByFrequency(String[] queries, String[] words) {
int[] queriesMinFrequecies = newint[queries.length];
for (inti = 0; i < queries.length; i++) {
queriesMinFrequecies[i] = computeLowestFrequency(queries[i]);
 }

int[] wordsMinFrequecies = newint[words.length];
for (inti = 0; i < words.length; i++) {
wordsMinFrequecies[i] = computeLowestFrequency(words[i]);
 }
Arrays.sort(wordsMinFrequecies);

int[] result = newint[queries.length];
for (inti = 0; i < result.length; i++) {
result[i] = binarySearch(wordsMinFrequecies, queriesMinFrequecies[i]);
 }
returnresult;
 }

privateintbinarySearch(int[] nums, inttarget) {
intleft = 0;
intright = nums.length - 1;
while (left <= right) {
intmid = (left + right) / 2;
if (nums[mid] <= target) {
left = mid + 1;
 } else {
right = mid - 1;
 }
 }
returnnums.length - left;
 }

privateintcomputeLowestFrequency(Stringstring) {
char[] str = string.toCharArray();
Arrays.sort(str);
StringsortedString = newString(str);
intfrequency = 1;
for (inti = 1; i < sortedString.length(); i++) {
if (sortedString.charAt(i) == sortedString.charAt(0)) {
frequency++;
 } else {
break;
 }
 }
returnfrequency;
 }
 }
}