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

LeetCode第1170题[比较字符串最小字母出现频次]

典型的先预处理，再二分统计

题目本质：

对于每个queries[i]，计算：有多少个word 满足f(queries[i]) < f(word)

也就是：先求出查询串的f再去words里数有多少个f(word)比它大

优化思路

因为我们要反复问：

有多少个f(word)严格大于某个值

这很适合：先把所有f(word)算出来排序，对每个query的f用二分查找

怎么找第一个 > x 的位置---这就是标准二分模板

也可以理解成找：第一个>= x+1的位置

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; } }