1170. Compare Strings by Frequency of the Smallest Character
1170. Compare Strings by Frequency of the Smallest Character
- Binary Search
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] fw = new int[words.length];
for(int i = 0; i < fw.length; i++)
fw[i] = f(words[i]);
Arrays.sort(fw);
int[] result = new int[queries.length];
for(int i = 0; i < result.length; i++) {
result[i] = getCnt(fw, f(queries[i]));
}
return result;
}
// find the first index that arr[index] > target
public int getCnt(int[] arr, int target) {
int l = 0, r = arr.length;
while(l < r) {
int mid = l + (r-l) / 2;
if(arr[mid] <= target) l = mid+1;
else r = mid;
}
return arr.length - l;
}
public int f(String s) {
int[] arr = new int[26];
for(char c : s.toCharArray())
arr[c-'a']++;
for(int i : arr)
if(i > 0)
return i;
return 0;
}