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=1l=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;}
};