Medium
题目描述
给你一个长度为 n 的整数数组 nums 和一个整数 k。
如果 nums 中的一个元素满足：数组中至少有 k 个元素严格大于它，那么这个元素被称为"合格的"。
返回 nums 中合格元素的总数。
示例 1：
输入：nums = [3,1,2], k = 1
输出：2
解释：
元素 1 和 2 都至少有 k = 1 个元素大于它们。
没有元素大于 3。因此，答案是 2。
示例 2：
输入：nums = [5,5,5], k = 2
输出：0
解释：
由于所有元素都等于 5，没有元素大于其他元素。因此，答案是 0。
约束条件：
- 1 <= n == nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 0 <= k < n
解题思路
这道题要求找出数组中有多少个元素，至少有 k 个元素严格大于它。
解题思路：
排序 + 统计法：先对数组排序，这样我们可以很容易地计算出每个元素有多少个更大的元素。对于排序后位置 i 的元素，有 n-i-1 个元素在它右边，但由于可能有重复元素，我们需要找到第一个大于当前元素的位置。
哈希表 + 二分查找法（推荐）：
- 使用哈希表统计每个不同值的出现次数
- 将所有不同的值排序
- 对于每个值，使用二分查找找到第一个大于它的值的位置
- 计算大于当前值的所有元素个数，如果 ≥ k，则将当前值的出现次数加入答案
这种方法的优势在于：
- 避免了重复计算相同值的情况
- 时间复杂度较优
- 代码简洁清晰
具体实现：
- 用哈希表记录每个值的出现次数
- 提取所有不同的值并排序
- 对每个值，通过二分查找确定有多少个更大的元素
- 如果满足条件，累加该值的出现次数
代码实现
class Solution {
public:
int countElements(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
vector<int> values;
for (auto& p : count) {
values.push_back(p.first);
}
sort(values.begin(), values.end());
int ans = 0;
int n = nums.size();
for (int val : values) {
auto it = upper_bound(values.begin(), values.end(), val);
int greaterCount = 0;
for (auto iter = it; iter != values.end(); iter++) {
greaterCount += count[*iter];
}
if (greaterCount >= k) {
ans += count[val];
}
}
return ans;
}
};
class Solution:
def countElements(self, nums: List[int], k: int) -> int:
from collections import Counter
import bisect
count = Counter(nums)
values = sorted(count.keys())
n = len(nums)
ans = 0
for val in values:
idx = bisect.bisect_right(values, val)
greater_count = sum(count[values[i]] for i in range(idx, len(values)))
if greater_count >= k:
ans += count[val]
return ans
public class Solution {
public int CountElements(int[] nums, int k) {
var count = new Dictionary<int, int>();
foreach (int num in nums) {
count[num] = count.GetValueOrDefault(num, 0) + 1;
}
var values = count.Keys.ToList();
values.Sort();
int ans = 0;
foreach (int val in values) {
int idx = BinarySearchUpper(values, val);
int greaterCount = 0;
for (int i = idx; i < values.Count; i++) {
greaterCount += count[values[i]];
}
if (greaterCount >= k) {
ans += count[val];
}
}
return ans;
}
private int BinarySearchUpper(List<int> arr, int target) {
int left = 0, right = arr.Count;
while (left < right) {
int mid = left + (right - left) / 2;
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
var countElements = function(nums, k) {
const count = new Map();
for (const num of nums) {
count.set(num, (count.get(num) || 0) + 1);
}
const values = Array.from(count.keys()).sort((a, b) => a - b);
const upperBound = (arr, target) => {
let left = 0, right = arr.length;
while (left < right) {
const mid = Math.floor(left + (right - left) / 2);
if (arr[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
};
let ans = 0;
for (const val of values) {
const idx = upperBound(values, val);
let greaterCount = 0;
for (let i = idx; i < values.length; i++) {
greaterCount += count.get(values[i]);
}
if (greaterCount >= k) {
ans += count.get(val);
}
}
return ans;
};
复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(m log m + m²) | m 是不同元素个数，排序 O(m log m)，每个元素计算后缀和 O(m) |
| 空间复杂度 | O(m) | 哈希表和排序数组的空间 |
优化版本时间复杂度： O(m log m + m)，通过预计算后缀和可以优化到线性时间计算每个元素的大于数量。