题目：
给你一个整数数组 nums 。数组 nums 的 唯一性数组 是一个按元素从小到大排序的数组，包含了 nums 的所有非空子数组中不同元素的个数。
换句话说，这是由所有 0 <= i <= j < nums.length 的 distinct(nums[i..j]) 组成的递增数组。
其中，distinct(nums[i..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 <= 1051 <= nums[i] <= 105
暴力枚举所有子数组
思路：
暴力滑动窗口枚举元素，无须多盐
代码：
class Solution {
public:
int medianOfUniquenessArray(vector<int>& nums) {
// 思路1：滑动窗口，枚举所有子数组，统计子数组中不同元素的个数时间复杂度O(n^2 + nlogn)
int n = nums.size();
vector<int> distinct(n * (n + 1) / 2, 1);
int idx = n;
for (int i = 2; i <= n; i++) { // 滑动窗口长度
unordered_map<int, int> window;
for (int j = 0; j < n; j++) {
if (j < i) {
window[nums[j]]++;
continue;
}
distinct[idx++] = window.size();
if (window[nums[j - i]] == 1) window.erase(nums[j - i]);
else window[nums[j - i]]--;
window[nums[j]]++;
if (j == n - 1) distinct[idx++] = window.size();
}
if (i == n) distinct[idx++] = window.size(); // 统计原数组的不同元素个数
}
sort(distinct.begin(), distinct.end());
if (n * (n + 1) / 2 % 2) return distinct[n * (n + 1) / 2 / 2]; // 奇数个
return distinct[n * (n + 1) / 2 / 2 - 1];
}
};
二分搜索优化
思路：
提示 1：二分答案
nums 的唯一性数组有多少个？也就是 nums 的非空连续子数组的个数。
长为 n 的子数组有 1 个，长为 n − 1 的子数组有 2 个，……，长为 1 的子数组有 n 个。
所有一共有 m = 1 + 2 + ⋯ + n = n * (n + 1) / 2 个非空连续子数组。
这 m 个子数组，对应着 m 个 distinct 值。
中位数是这 m 个数中的第 k=⌈m / 2⌉ 小元素。例如 m = 4 时，中位数是其中第 2 小元素。
考虑这 m 个数中，小于等于某个定值 upper 的数有多少个。
由于 upper 越大，小于等于 upper 的数越多，有单调性，故可以二分中位数为 upper，问题变成：
distinct 值 ≤ upper 的子数组有多少个？
设子数组的个数为 cnt，如果 cnt<k 说明二分的 upper 小了，更新二分左边界 left，否则更新二分右边界 right。
提示 2：滑动窗口
怎么计算 distinct 值 ≤ upper 的子数组个数？
由于子数组越长，不同元素个数（distinct 值）不会变小，有单调性，故可以用滑动窗口计算子数组个数。
用一个哈希表 freq 统计窗口（子数组）内的元素及其出现次数。
枚举窗口右端点 r，把 nums[r] 加入 freq（出现次数加一）。如果发现 freq 的大小超过 upper，说明窗口内的元素过多，那么不断移出窗口左端点元素 nums[l]（出现次数减一，如果出现次数等于 0 就从 freq 中移除），直到 freq 的大小 ≤ upper 为止。
此时右端点为 r，左端点为 l, l + 1, l + 2, ⋯, r 的子数组都是满足要求的（distinct 值 ≤ upper），一共有 r − l + 1 个，加到子数组个数 cnt 中。
其它细节
开区间二分左边界：0，一定不满足要求，因为没有子数组的 distinct 值是 0。
开区间二分右边界：n，或者 nums 中的不同元素个数，一定满足要求，因为所有子数组的 distinct 值都不超过 n。
用开区间计算二分仅仅是个人喜好，你也可以使用闭区间或半闭半开区间计算二分，并无本质区别。
答疑
问：为什么二分出来的答案，一定是某个子数组的 distinct 值？有没有可能，二分出来的答案不是任何子数组的 distinct 值？
答：反证法。如果答案 d 不是任何子数组的 distinct 值，那么 distinct 值 ≤d 和 ≤d−1 算出来的子数组个数是一样的。也就是说 d−1 同样满足要求，即 check(d - 1) == true，这与循环不变量相矛盾。
代码：
class Solution {
public:
int medianOfUniquenessArray(vector<int>& nums) {
int n = nums.size();
long long k = ((long long) n * (n + 1) / 2 + 1) / 2;
auto check = [&](int upper) {
long long cnt = 0;
int l = 0;
unordered_map<int, int> freq;
for (int r = 0; r < n; r++) {
freq[nums[r]]++; // 移入右端点
while (freq.size() > upper) { // 窗口内元素过多
int out = nums[l++];
if (--freq[out] == 0) { // 移出左端点
freq.erase(out);
}
}
cnt += r - l + 1; // 右端点固定为 r 时，有 r-l+1 个合法左端点
if (cnt >= k) {
return true;
}
}
return false;
};
int left = 0, right = n;
while (left + 1 < right) {
int mid = (left + right) / 2;
(check(mid) ? right : left) = mid;
}
return right;
}
};