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

LeetCode 3134. 找出唯一性数组的中位数 Java 实现题目简析题意给定数组 nums 生成其所有子数组对每个子数组计算不同元素的个数得到「唯一性数组」。求该数组的中位数。关键点1. 子数组总数n nums.length子数组总个数 total \dfrac{n(n1)}{2}2. 中位数位置若数组长度为 m中位数是第 \lceil m/2 \rceil 小的数1-index3. 核心思路二分答案 滑动窗口统计不同元素个数 \le mid 的子数组数量解题思路1. 二分值域唯一性取值范围是 [1, n]二分枚举答案 k。2. 滑动窗口计数用双指针统计「不同元素数量 \le k」的子数组总数 cnt 。3. 二分判定- 若 cnt 中位数位次 说明答案在左半区间收缩右边界- 否则答案在右半区间收缩左边界Java 完整代码javaimport 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-indexlong 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) {MapInteger, 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 1res r - l 1;}return res;}}复杂度分析- 时间复杂度O(n \log n)二分次数O(\log n)每次滑动窗口遍历数组O(n)- 空间复杂度O(n)哈希表存储元素频次补充说明1. 数据类型注意子数组总数会达到 \dfrac{n(n1)}{2}n 最大可取 10^5结果会溢出 int 必须用 long 存计数、位次。2. 中位数位置推导举例- m5位次 (51)/23第 3 小- m4位次 (41)/22整数除法第 2 小符合题目中位数定义。3. 滑动窗口逻辑固定右端点 r 找到最小左端点 l 区间 [l,r] 内不同元素 \le k。以 r 结尾的合法子数组数量 r-l1累加即可。优化数组替代 HashMap提速若元素值域不大可用数组替代哈希表进一步提速javapublic 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;}}该版本在大数据用例下运行更快适合题目数据范围。