DeepSeek LeetCode 3636. 查询超过阈值频率最高元素 Java实现

核心解题思路这道题是典型的静态区间众数查询问题。最直接的方法是预处理每个元素出现的位置然后对每个查询在候选元素中二分统计区间频率复杂度在题目的约束下是可行的 (n ≤ 10^4, queries ≤ 5*10^4)。更高效的解法是分块预处理把数组分成大小约为 sqrt(n) 的块预处理出 pmx[i][j] 表示第 i 块到第 j 块的众数。查询时将区间分为“中间完整块 左右零散部分”候选众数只可能是中间块的预处理的众数以及左右零散部分出现过的元素。用位置列表 二分查找来统计这些候选元素在区间内的实际出现次数找出满足阈值且频率最高的最小元素。Java 实现1. 方案一位置列表 二分查找简单版javaimport java.util.*;class Solution {public int[] subarrayMajority(int[] nums, int[][] queries) {// 1. 预处理每个元素的所有出现位置MapInteger, ListInteger pos new HashMap();for (int i 0; i nums.length; i) {pos.computeIfAbsent(nums[i], k - new ArrayList()).add(i);}int[] ans new int[queries.length];for (int i 0; i queries.length; i) {int l queries[i][0], r queries[i][1], threshold queries[i][2];int bestNum -1, bestFreq 0;// 2. 遍历所有不同的元素作为候选可优化为只遍历高频候选for (Map.EntryInteger, ListInteger entry : pos.entrySet()) {int num entry.getKey();ListInteger list entry.getValue();// 二分查找区间 [l, r] 内的出现次数int left lowerBound(list, l);int right upperBound(list, r);int freq right - left;if (freq threshold) {if (freq bestFreq || (freq bestFreq num bestNum)) {bestFreq freq;bestNum num;}}}ans[i] bestNum;}return ans;}private int lowerBound(ListInteger list, int target) {int lo 0, hi list.size();while (lo hi) {int mid lo (hi - lo) / 2;if (list.get(mid) target) lo mid 1;else hi mid;}return lo;}private int upperBound(ListInteger list, int target) {int lo 0, hi list.size();while (lo hi) {int mid lo (hi - lo) / 2;if (list.get(mid) target) lo mid 1;else hi mid;}return lo;}}2. 方案二分块最优解ACjavaimport java.util.*;class Solution {public int[] subarrayMajority(int[] nums, int[][] queries) {return new BlockDiv(nums).queryAll(queries);}class BlockDiv {private int n, size, blockCnt;private int[] nums;private int[][] pmx; // pmx[i][j] 块 i 到块 j 的众数private MapInteger, ListInteger pos;public BlockDiv(int[] nums) {this.n nums.length;this.size (int) Math.sqrt(n) 1;this.blockCnt (n size - 1) / size;this.nums nums;// 预处理块间众数pmx new int[blockCnt][blockCnt];for (int i 0; i blockCnt; i) {MapInteger, Integer cnt new HashMap();int mode 0, maxCnt 0;for (int j i; j blockCnt; j) {for (int k j * size; k Math.min((j 1) * size, n); k) {int num nums[k];int c cnt.getOrDefault(num, 0) 1;cnt.put(num, c);if (c maxCnt || (c maxCnt num mode)) {maxCnt c;mode num;}}pmx[i][j] mode;}}// 预处理每个元素的位置列表pos new HashMap();for (int i 0; i n; i) {pos.computeIfAbsent(nums[i], k - new ArrayList()).add(i);}}// 查询区间 [l, r] 的答案private int query(int l, int r, int threshold) {int lb l / size, rb r / size;// 同一块或相邻块暴力统计if (lb rb || lb 1 rb) {MapInteger, Integer cnt new HashMap();int mode 0, maxCnt 0;for (int i l; i r; i) {int num nums[i];int c cnt.getOrDefault(num, 0) 1;cnt.put(num, c);if (c maxCnt || (c maxCnt num mode)) {maxCnt c;mode num;}}return maxCnt threshold ? mode : -1;}// 候选众数中间块的众数 左/右零散部分的所有元素ListInteger candidates new ArrayList();candidates.add(pmx[lb 1][rb - 1]);for (int i l; i (lb 1) * size; i) candidates.add(nums[i]);for (int i rb * size; i r; i) candidates.add(nums[i]);int bestNum -1, bestFreq 0;for (int num : candidates) {ListInteger list pos.get(num);if (list null) continue;int left lowerBound(list, l);int right upperBound(list, r);int freq right - left;if (freq threshold) {if (freq bestFreq || (freq bestFreq num bestNum)) {bestFreq freq;bestNum num;}}}return bestNum;}public int[] queryAll(int[][] queries) {int[] res new int[queries.length];for (int i 0; i queries.length; i) {res[i] query(queries[i][0], queries[i][1], queries[i][2]);}return res;}private int lowerBound(ListInteger list, int target) {int lo 0, hi list.size();while (lo hi) {int mid lo (hi - lo) / 2;if (list.get(mid) target) lo mid 1;else hi mid;}return lo;}private int upperBound(ListInteger list, int target) {int lo 0, hi list.size();while (lo hi) {int mid lo (hi - lo) / 2;if (list.get(mid) target) lo mid 1;else hi mid;}return lo;}}}复杂度· 方案一预处理 O(n)每次查询 O(U log n)U 为不同元素个数最坏 O(n log n)· 分块方案预处理 O(n√n)每次查询 O(√n log n)