3134. 找出唯一性数组的中位数（24.8.27）

前言

本次通过学习 灵茶山艾府 的代码进行解题研究

题目

题目描述：

给你一个整数数组 nums 。数组 nums 的唯一性数组是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。

换句话说，这是由所有 0 <= i <= j < nums.Length 的 distinct(nums[i..j]) 组成的递增数组。其中，distinct(nums[..j]) 表示从下标 i 到下标 j 的子数组中不同元素的数量。

返回 nums 唯一性数组的中位数。

注意，数组的中位数定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个。

示例 1：

输入：nums=[1,2,3]

输出：1

解释：

nums 的唯一性数组为 [distinct(nums[(0..0)], distinct(nums[1..1]), distinct(nums [2.2]), distinct(nums[0..1]), distinct(nums[1..2]), distinct(nums[0..2])]，即 [1,1,1,2,2,3] 。唯一性数组的中位数为 1 ，因此答案是 1 。


示例 2：

输入：nums=[3,4,3,4,5]

输出：2

解释：

nums 的唯一性数组为 [1,1,1,1,1,2,2,2,2,2,2,2,3,3,3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

示例 3：

输入：nums=[4,3,5,4]

输出：2

解释：

nums 的唯一性数组为 [1,1,1,1,2,2,2,3,3,3] 。唯一性数组的中位数为 2 ，因此答案是 2 。

提示：

• 1<=nums.Length<=105

• 1<=nums[i]<=105

解题思路

见代码

代码

/*
子数组 是数组中连续的 非空 元素序列
子集的个数 :
            子集中数的个数: 1 2   3   4    ... n
            这个子集的个数: n n-1 n-2 n-3  ... 1
            数总和（由等差数列求和得）：（n+1）*n/2

中位数：数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素，则取值较小的那个
       假设一个数组有 3 个数，则中位数是 1
       假设一个数组有 4 个数，则中位数是 1
       假设一个数组有 2k+1 个数，则中位数是 k+1【((2k+1)+1)/2】
       假设一个数组有 2k 个数，则中位数是 k-1 【(2k+1)/2】
       -->假设一个数组有 n 个数，则中位数是 (n+1)/2


*/
class Solution {
public:
    int medianOfUniquenessArray(vector<int>& nums) {
        int n=nums.size();
        long long k=((long long)n*(n+1)/2+1)/2;//数组的个数
        /*
        设子数组的个数为 cnt，如果 cnt<k 
        说明二分的 m 小了，更新二分左边界 left，否则更新二分右边界 right
        */
        auto solve=[&](int m){
            long long cnt=0;
            int left=0;
            unordered_map<int, int> h;//记录次数
            //滑动窗口的模板
            //先固定左端，移动右端
            for(int left=0,right=0;right<n;right++){
                h[nums[right]]++;
                //当大于 m 即大于了的子数组个数
                //窗户口元素过多了
                while(h.size()>m){
                    h[nums[left]]--;//减去多余的统计个数
                    if(h[nums[left]]==0){
                        h.erase(nums[left]);//删除多余的窗口统计
                    }
                    left++;//将左边界向右移动一位
                }
                cnt+=right-left+1; // 右端点固定为 r 时，有 r-l+1 个合法左端点
                if(cnt>=k) return true;
            }
            return false;
        };
        int l=0,r=n;
        /*
        二分的内容是 distinct的数组中的内容
        比如实例1：
        nums = [1,2,3],distinct=[1, 1, 1, 2, 2, 3], ans=1
        l=0,r=3,mid=1，k=3
        进入solve当中，
        进行第一轮操作后，left=0,right=0，h.size()=1，cnt=1<k
        进行第二轮操作后，left=0,right=1，h.size()=2>m,窗口滑动一次,left++,cnt=2<k
        进行第三轮操作后，left=1,right=2，h.size()=2>m,窗口滑动一次,left++,cnt=3=k，即此刻说明我所组成的子数组数已经达到我所求的k的位置
        */
        while(l+1<r){
            int mid=(l+r)/2;
            if(solve(mid)) r=mid;
            else l=mid;
        }
        return r;
    }
};