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

稚辉君.MCA.P9.JAVA

195人浏览 · 2026-07-20 07:22:06

稚辉君.MCA.P9.JAVA · 2026-07-20 07:22:06 发布

核心解题思路

这道题是典型的静态区间众数查询问题。最直接的方法是预处理每个元素出现的位置，然后对每个查询，在候选元素中二分统计区间频率，复杂度在题目的约束下是可行的 (n ≤ 10^4, queries ≤ 5*10^4)。

更高效的解法是分块预处理：把数组分成大小约为 sqrt(n) 的块，预处理出 pmx[i][j] 表示第 i 块到第 j 块的众数。查询时，将区间分为“中间完整块 + 左右零散部分”，候选众数只可能是中间块的预处理的众数以及左右零散部分出现过的元素。用位置列表 + 二分查找来统计这些候选元素在区间内的实际出现次数，找出满足阈值且频率最高的最小元素。

Java 实现

1. 方案一：位置列表 + 二分查找（简单版）

```java
import java.util.*;

class Solution {
public int[] subarrayMajority(int[] nums, int[][] queries) {
// 1. 预处理每个元素的所有出现位置
Map<Integer, List<Integer>> 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.Entry<Integer, List<Integer>> entry : pos.entrySet()) {
int num = entry.getKey();
List<Integer> 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(List<Integer> 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(List<Integer> 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. 方案二：分块（最优解）AC

```java
import 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 Map<Integer, List<Integer>> 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++) {
Map<Integer, 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) {
Map<Integer, 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;
}

// 候选众数：中间块的众数 + 左/右零散部分的所有元素
List<Integer> 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) {
List<Integer> 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;
}