Easy

题目描述

给你一个非负整数数组 nums。如果存在一个数 x，使得 nums 中恰好有 x 个元素大于或者等于 x，那么就称 nums 是特殊的。

注意：x 不必是 nums 的中的元素。

返回 x。如果数组不是特殊的，则返回 -1。可以证明的是，如果 nums 是特殊的，那么 x 是唯一的。

示例 1：

输入：nums = [3,5]
输出：2
解释：有 2 个值（3 和 5）大于或等于 2 。

示例 2：

输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组。

示例 3：

输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个值大于或等于 3 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000

解题思路

解题思路

这道题要求找到一个特殊的数 x，使得数组中恰好有 x 个元素大于或等于 x。

方法一：暴力枚举（推荐）

由于 x 表示大于或等于它的元素个数，所以 x 的取值范围是 [0, n]，其中 n 是数组长度。我们可以逐一检查每个可能的 x 值：

  • 对于每个 x，统计数组中大于或等于 x 的元素个数
  • 如果个数恰好等于 x，则找到了答案
  • 如果所有可能的 x 都不满足条件，返回 -1

方法二：排序优化

先对数组进行排序，然后利用排序后的性质快速计算大于或等于 x 的元素个数。排序后，如果有 count 个元素大于或等于 x，这些元素都位于数组的后 count 位。

时间复杂度方面，暴力法为 O(n²)，排序法为 O(n log n)。但由于数组长度最大为 100，暴力法的常数更小，实际表现更好。

代码实现

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int n = nums.size();
        
        for (int x = 0; x <= n; x++) {
            int count = 0;
            for (int num : nums) {
                if (num >= x) {
                    count++;
                }
            }
            if (count == x) {
                return x;
            }
        }
        
        return -1;
    }
};

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        n = len(nums)
        
        for x in range(n + 1):
            count = sum(1 for num in nums if num >= x)
            if count == x:
                return x
        
        return -1

public class Solution {
    public int SpecialArray(int[] nums) {
        int n = nums.Length;
        
        for (int x = 0; x <= n; x++) {
            int count = 0;
            foreach (int num in nums) {
                if (num >= x) {
                    count++;
                }
            }
            if (count == x) {
                return x;
            }
        }
        
        return -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var specialArray = function(nums) {
    for (let x = 0; x <= nums.length; x++) {
        let count = 0;
        for (let num of nums) {
            if (num >= x) count++;
        }
        if (count === x) return x;
    }
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型暴力枚举排序优化
时间复杂度O(n²)O(n log n)
空间复杂度O(1)O(1)