3134. 找出唯一性数组的中位数
3134. 找出唯一性数组的中位数
题目链接:3134. 找出唯一性数组的中位数
代码如下:
class Solution
{
public:int medianOfUniquenessArray(vector<int>& nums){long long m = (1LL + nums.size()) * nums.size() / 2;int left = 0, right = nums.size();auto check = [&](int mx)->bool{unordered_map<int, int> count;long long k = 0;for (int left = 0, right = 0; right < nums.size(); ++right){int x = nums[right];++count[x];while (count.size() > mx){int y = nums[left++];if (--count[y] == 0){count.erase(y);}}k += right - left + 1;if (k >= (m + 1) / 2){return true;}}return false;};while (left < right){int mid = (left + right) >> 1;if (check(mid)){right = mid;}else{left = mid + 1;}}return left;}
};