题解 | 找出唯一性数组的中位数

题干解析:

题目大意如下:

• 首先对于一个长为n的数组,其至少有n*(n-1)/2个子数组,将这些子数组中所包含的元素个数作为元素记录在另一个数组中,同时确保数组升序,我们得到的数组即为题设的唯一性数组
• 然后题目要求我们寻找这个升序数组的中位数,同时如果中位数有两个,则取最小的那个.

算法逻辑:

最先想到的几乎都是直接暴力枚举出唯一性数组,然后取出其中的中位数,并返回,但这里数据量最高为 n=100000,因此,直接枚举的话需要循环10^10次,显然会超时,再者,在分析题目时我刻意没有说我们需要得到完整的唯一性数组,确实,针对这道题,我们没必要得到完整的唯一性数组.

首先我们确定数组的中位数所在位置k,假设一个数组有n个值,那么中位应当为:

针对唯一性数组,我们要么找到此数组的低于一个数upper的值有少于k个,那么我们便能确定中位数ans > upper,反之ans <= upper.然后唯一性数组值小于upper的个数意味着什么呢,upper意味着某个子数组元素个数为upper,因此这个值意味着数组的所有子数组中元素个数不大于upper的个数.

由此我们不妨使用双指针或滑动窗口对数组进行划分子数组,同时计数.不仅如此,不难发现,一个子数组的子数组其元素个数一点小于等于该子数组,针对这个特性我们便能够省去反复前移右指针的位置(即右指针只需要一直右移即可,达到最大的元素个数(upper)时在计数即可).

现在我们能够依据upper来压缩ans的取值范围了,之后的操作便是通过二分法反复压缩ans的取值范围直至将其逼至某个值,那个值便是我们所需的答案.

实现代码:

int medianOfUniquenessArray(vector<int>& nums) {
    const int n = static_cast<int>(nums.size());
    const int64_t k = (static_cast<int64_t>(n) * (n + 1) / 2 + 1) / 2; // k值可能很大,因此使用long long(int64_t)

    auto check = [&](const int upper) -> bool {
        int64_t cnt = 0; // 符合要求的子数组个数
        int left =0; // 左指针
        unordered_map<int, int> freq; // 计频器,可以用数组代替
        for (int right = 0; right < n; ++right) {
            freq[nums[right]]++;
            while (freq.size() > upper) { // 窗口元素个数多于了upper,不符合要求了,因此需要去除至少一种元素
                int out = nums[left];
                ++left;
                --freq[out];
                if (freq[out] == 0) freq.erase(out);
            }
            cnt += right - left + 1; // 累加符合要求的子数列个数,这里子数列均保证以left为起点,因此是线性的,不与要相乘
            if (cnt >= k) return true; // 有多于k个的窗口数(子数列数)
        }
        return false; // 符合要求窗口总数小于k个
    };

  	// 二分模板,但注意边界与判断函数返回的布尔值的含义
    int left = 0, right = n;
    while (left + 1 < right) {
        if (const int mid = (right + left) / 2; check(mid)) right = mid;
        else left = mid;
    }

    return right;
}

复杂度分析:

• 时间复杂度: 二分模板基础复杂度为O(log n), 针对判断函数,每个窗口元素最多进出一次窗口,总计为O(n),二者结合,总时间复杂度为O(nlog n).
• 空间复杂度: 哈希表计数开销为O(n),其余额外空间开销为O(1),总计O(n).