【二分法，双指针】3134.找出唯一性数组的中位数

Problem: 3134. 找出唯一性数组的中位数
难度分2451，这里记录对于官解的理解。

思路

观察提示中数组的长度，可知这题使用$O(n^2)$复杂度的解法都会超时，而所有非空子数组共有n*(n+1)/2个，显然是不可行的。因此需要考虑二分法。如果二分法可行，再加上数组的单遍遍历，复杂度为$O(nlogn)$，就不会超时。

要使用二分法，首先我们需要保证二分查找的数组是有序的。

这里的有序是广义的有序，只需要保证在某个性质上是有序的即可。

首先，我们观察到t越大，唯一性数组中t出现的次数不一定越多，这个性质可以排除。

因此另找一个性质。对于以答案为下标的数组，设t为答案的某个值（即数组下标），对于性质数组nums中不同元素个数不大于t的非空子数组个数ct，该数组是有序的。也就是说，t的值越大，ct的值也就越大。

这里数组的元素是累加性质的，所以一定递增，可以作为一种二分的思考选择。

同时我们可以注意到，对于不同元素个数为t的nums数组切片nums[j...i]，其子数组的不同元素个数也不大于t。如果我们使用下标i遍历nums数组，并且每一轮都把j到i之间的取值作为左端点，i作为右端点的所有i-j+1个数组累加到ct中，我们最后就可以得到ct的值。

而j和i的值都可以通过滑动窗口来找到，用一个哈希表来存储不同元素的个数，大于t时下把j右移并更新哈希表，直到哈希表的元素个数不大于t。

使用滑动窗口才能达成$O(n)$复杂度，对于子数组的问题非常有用。

对于二分答案，上界为n，下界为1，我们要寻找的中位数在数组的(n*(n+1)/2+1)/2的位置上，只要找到不小于该数的最小ct值，t就是要求的答案。

复杂度

• 时间复杂度: $O(nlogn)$：二分法$logn$，滑动窗口$n$。
• 空间复杂度: $O(n)$：哈希表的开销。

Code

class Solution {
    public int medianOfUniquenessArray(int[] nums) {
        int n = nums.length;
        long median = ((long) n * (n + 1) / 2 + 1) / 2;
        int res = 0;
        int lo = 1, hi = n;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;
            if (check(nums, mid, median)) {
                res = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return res;
    }
    // 检测数组中不同元素数目小于等于 t 的连续子数组数目是否大于等于 median
    public boolean check(int[] nums, int t, long median) {
        HashMap<Integer, Integer> cnt = new HashMap<>();
        long tot = 0;
        for (int i = 0, j = 0; i < nums.length; i++) {
            cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
            while (cnt.size() > t) {
                cnt.put(nums[j], cnt.get(nums[j]) - 1);
                if (cnt.get(nums[j]) == 0) {
                    cnt.remove(nums[j]);
                }
                j++;
            }
            tot += i - j + 1;
        }
        return tot >= median;
    }
}