跳转至

3759. 统计合格元素的数目

题目描述

给你一个长度为 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 <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k < n

解法

方法一：排序

如果 \(k = 0\)，那么数组中所有元素均为合格元素，直接返回数组长度即可。

否则，我们对数组进行排序，记排序后数组长度为 \(n\)。对于每个下标 \(i\) 满足 \(0 \\leq i < n - k\) 的元素，如果它严格小于下标为 \(n - k\) 的元素，则它是一个合格元素。我们只需统计这样的元素个数并返回即可。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组 \(\textit{nums}\) 的长度。

1
2
3
4
5
6
7
class Solution:
    def countElements(self, nums: List[int], k: int) -> int:
        n = len(nums)
        if k == 0:
            return n
        nums.sort()
        return sum(nums[n - k] > nums[i] for i in range(n - k))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int countElements(int[] nums, int k) {
        int n = nums.length;
        if (k == 0) {
            return n;
        }
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 0; i < n - k; ++i) {
            if (nums[n - k] > nums[i]) {
                ++ans;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int countElements(vector<int>& nums, int k) {
        int n = nums.size();
        if (k == 0) {
            return n;
        }
        ranges::sort(nums);
        int ans = 0;
        for (int i = 0; i < n - k; ++i) {
            if (nums[n - k] > nums[i]) {
                ++ans;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countElements(nums []int, k int) int {
    n := len(nums)
    if k == 0 {
        return n
    }
    sort.Ints(nums)
    ans := 0
    for i := 0; i < n-k; i++ {
        if nums[n-k] > nums[i] {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function countElements(nums: number[], k: number): number {
    const n = nums.length;
    if (k === 0) {
        return n;
    }
    nums.sort((a, b) => a - b);
    let ans = 0;
    for (let i = 0; i < n - k; ++i) {
        if (nums[n - k] > nums[i]) {
            ++ans;
        }
    }
    return ans;
}

评论