豆包 LeetCode 3134. 找出唯一性数组的中位数 Java实现

LeetCode 3134. 找出唯一性数组的中位数 Java 实现

题目简析

题意
给定数组 nums ，生成其所有子数组，对每个子数组计算不同元素的个数，得到「唯一性数组」。求该数组的中位数。

关键点：

1. 子数组总数：n = nums.length，子数组总个数 total = \dfrac{n(n+1)}{2}
2. 中位数位置：若数组长度为 m，中位数是第 \lceil m/2 \rceil 小的数（1-index）
3. 核心思路：二分答案 + 滑动窗口（统计不同元素个数 \le mid 的子数组数量）



解题思路

1. 二分值域：唯一性取值范围是 [1, n]，二分枚举答案 k。
2. 滑动窗口计数：用双指针统计「不同元素数量 \le k」的子数组总数 cnt 。
3. 二分判定：
- 若 cnt >= 中位数位次 ：说明答案在左半区间，收缩右边界
- 否则：答案在右半区间，收缩左边界



Java 完整代码

java
import java.util.HashMap;
import java.util.Map;

public class Solution {
public int medianOfUniquenessArray(int[] nums) {
int n = nums.length;
// 所有子数组总数
long total = (long) n * (n + 1) / 2;
// 中位数是第 pos 小（1-index）
long pos = (total + 1) / 2;

int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
long count = countSubarray(nums, mid);
if (count >= pos) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

// 统计：不同元素个数 <= k 的子数组数量
private long countSubarray(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
int l = 0;
long res = 0;
for (int r = 0; r < nums.length; r++) {
int cur = nums[r];
freq.put(cur, freq.getOrDefault(cur, 0) + 1);

// 不同元素超过 k，左指针右移
while (freq.size() > k) {
int leftVal = nums[l];
freq.put(leftVal, freq.get(leftVal) - 1);
if (freq.get(leftVal) == 0) {
freq.remove(leftVal);
}
l++;
}
// 以 r 为右端点的合法子数组数量：r - l + 1
res += r - l + 1;
}
return res;
}
}




复杂度分析

- 时间复杂度：O(n \log n)
二分次数：O(\log n)，每次滑动窗口遍历数组：O(n)
- 空间复杂度：O(n)，哈希表存储元素频次



补充说明

1. 数据类型注意
子数组总数会达到 \dfrac{n(n+1)}{2}，n 最大可取 10^5，结果会溢出 int ，必须用 long 存计数、位次。
2. 中位数位置推导
举例：
- m=5：位次 (5+1)/2=3，第 3 小
- m=4：位次 (4+1)/2=2（整数除法），第 2 小
符合题目中位数定义。
3. 滑动窗口逻辑
固定右端点 r ，找到最小左端点 l ，区间 [l,r] 内不同元素 \le k。
以 r 结尾的合法子数组数量 = r-l+1，累加即可。



优化（数组替代 HashMap，提速）

若元素值域不大，可用数组替代哈希表，进一步提速：

java
public class Solution {
static final int MAX = (int) 1e6 + 10;
int[] freq = new int[MAX];

public int medianOfUniquenessArray(int[] nums) {
int n = nums.length;
long total = (long) n * (n + 1) / 2;
long pos = (total + 1) / 2;

int left = 1, right = n;
while (left < right) {
int mid = left + (right - left) / 2;
long count = countSubarray(nums, mid);
if (count >= pos) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

private long countSubarray(int[] nums, int k) {
// 重置频次数组
java.util.Arrays.fill(freq, 0);
int l = 0, diff = 0;
long res = 0;
for (int r = 0; r < nums.length; r++) {
int cur = nums[r];
if (freq[cur] == 0) diff++;
freq[cur]++;

while (diff > k) {
int leftVal = nums[l];
freq[leftVal]--;
if (freq[leftVal] == 0) diff--;
l++;
}
res += r - l + 1;
}
return res;
}
}


该版本在大数据用例下运行更快，适合题目数据范围。