class Solution {
public:
int medianOfUniquenessArray(vector<int>& nums) {
}
};
3134. 找出唯一性数组的中位数
给你一个整数数组 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原站题解
cpp 解法, 执行用时: 1646 ms, 内存消耗: 363.4 MB, 提交时间: 2024-05-01 11:00:49
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;
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;
}
};
java 解法, 执行用时: 497 ms, 内存消耗: 60.1 MB, 提交时间: 2024-05-01 11:00:32
class Solution {
public int medianOfUniquenessArray(int[] nums) {
int n = nums.length;
long k = ((long) n * (n + 1) / 2 + 1) / 2;
int left = 0;
int right = n;
while (left + 1 < right) {
int mid = (left + right) / 2;
if (check(nums, mid, k)) {
right = mid;
} else {
left = mid;
}
}
return right;
}
private boolean check(int[] nums, int upper, long k) {
long cnt = 0;
int l = 0;
HashMap<Integer, Integer> freq = new HashMap<>();
for (int r = 0; r < nums.length; r++) {
freq.merge(nums[r], 1, Integer::sum);
while (freq.size() > upper) {
int out = nums[l++];
if (freq.merge(out, -1, Integer::sum) == 0) {
freq.remove(out);
}
}
cnt += r - l + 1;
if (cnt >= k) {
return true;
}
}
return false;
}
}
python3 解法, 执行用时: 3915 ms, 内存消耗: 33.9 MB, 提交时间: 2024-05-01 11:00:17
class Solution:
def medianOfUniquenessArray(self, nums: List[int]) -> int:
n = len(nums)
k = (n * (n + 1) // 2 + 1) // 2
def check(upper: int) -> bool:
cnt = l = 0
freq = Counter()
for r, in_ in enumerate(nums):
freq[in_] += 1
while len(freq) > upper:
out = nums[l]
freq[out] -= 1
if freq[out] == 0:
del freq[out]
l += 1
cnt += r - l + 1
if cnt >= k:
return True
return False
return bisect_left(range(len(set(nums))), True, 1, key=check)
golang 解法, 执行用时: 678 ms, 内存消耗: 10 MB, 提交时间: 2024-05-01 11:00:02
func medianOfUniquenessArray(nums []int) int {
n := len(nums)
k := (n*(n+1)/2 + 1) / 2
ans := 1 + sort.Search(n-1, func(upper int) bool {
upper++
cnt := 0
l := 0
freq := map[int]int{}
for r, in := range nums {
freq[in]++
for len(freq) > upper {
out := nums[l]
freq[out]--
if freq[out] == 0 {
delete(freq, out)
}
l++
}
cnt += r - l + 1
if cnt >= k {
return true
}
}
return false
})
return ans
}