LeetCode1170题解：预处理+二分查找

LeetCode第1170题[比较字符串最小字母出现频次]典型的先预处理再二分统计题目本质对于每个queries[i]计算有多少个word 满足f(queries[i]) f(word)也就是先求出查询串的f再去words里数有多少个f(word)比它大优化思路因为我们要反复问有多少个f(word)严格大于某个值这很适合先把所有f(word)算出来排序对每个query的f用二分查找怎么找第一个 x 的位置---这就是标准二分模板也可以理解成找第一个 x1的位置import java.util.Arrays; class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int n words.length; int[] w new int[n]; // 先算所有 words 的 f 值 for (int i 0; i n; i) { w[i] f(words[i]); } // 排序方便二分 Arrays.sort(w); int[] ans new int[queries.length]; for (int i 0; i queries.length; i) { int x f(queries[i]); // 找第一个 x 的位置 int idx upperBound(w, x); ans[i] n - idx; } return ans; } // 计算 f(s) private int f(String s) { char minChar z; int count 0; for (int i 0; i s.length(); i) { char c s.charAt(i); if (c minChar) { minChar c; count 1; } else if (c minChar) { count; } } return count; } // 返回第一个 target 的位置 private int upperBound(int[] nums, int target) { int l 0, r nums.length; while (l r) { int mid l (r - l) / 2; if (nums[mid] target) { l mid 1; } else { r mid; } } return l; } }