题目描述
给你一个整数数组 nums
。数组 nums
的 唯一性数组 是一个按元素从小到大排序的数组,包含了 nums
的所有非空子数组中不同元素的个数。
换句话说,这是由所有 0 <= i <= j < nums.length
的 distinct(nums[i..j])
组成的递增数组。
其中,distinct(nums[i..j])
表示从下标 i
到下标 j
的子数组中不同元素的数量。
返回 nums
唯一性数组 的 中位数。
注意,数组的 中位数 定义为有序数组的中间元素。如果有两个中间元素,则取值较小的那个。
样例
输入: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。
输入: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。
输入:nums = [4,3,5,4]
输出:2
解释:
nums 的唯一性数组为 [1, 1, 1, 1, 2, 2, 2, 3, 3, 3]。
唯一性数组的中位数为 2,因此答案是 2。
限制
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
算法
(二分答案) $O(U + n \log n)$
- 二分查找中位数 $x$,计算不同值小于等于 $x$ 的区间个数。
- 对于每个结尾位置 $i$,找到尽可能小的位置 $j$,满足 $[j, i]$ 内不同元素的个数小于等于 $x$。
- 注意到 $j$ 是随着 $i$ 单调不减的,可以使用双指针,在每次 $i$ 移动后调整 $j$。当前区间内的不同元素个数可以通过哈希表来维护。
时间复杂度
- 二分的区间为 $O(n)$,每次判定的时间复杂度为 $O(n)$。
- 维护全局的哈希数组 $O(U)$,其中 $U$ 是最大可能的数字。
- 故总时间复杂度为 $O(U + n \log n)$。
空间复杂度
- 需要 $O(U)$ 的额外空间存储哈希表。
C++ 代码
#define LL long long
const int U = 100010;
int seen[U];
class Solution {
private:
int n;
LL calc(int x, const vector<int> &nums) {
LL res = 0;
int cnt = 0, j = 0;
for (int i = 0; i < n; i++) {
if (++seen[nums[i]] == 1)
++cnt;
while (cnt > x)
if (--seen[nums[j++]] == 0)
--cnt;
res += i - j + 1;
}
while (j < n) // 清空 seen 数组,避免 memset
--seen[nums[j++]];
return res;
}
public:
int medianOfUniquenessArray(vector<int>& nums) {
n = nums.size();
int l = 1, r = n;
LL tot = (LL)(n) * (n + 1) / 2;
while (l < r) {
int mid = (l + r) >> 1;
if (calc(mid, nums) >= (tot + 1) / 2)
r = mid;
else
l = mid + 1;
}
return l;
}
};