特殊数组的特征值

难度: Easy

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

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

如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则，返回 -1 。可以证明的是，如果 nums 是特殊数组，那么其特征值 x 是 唯一的 。

示例 1：

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

示例 2：

输入：nums = [0,0]
输出：-1
解释：没有满足题目要求的特殊数组，故而也不存在特征值 x 。
如果 x = 0，应该有 0 个元素 >= x，但实际有 2 个。
如果 x = 1，应该有 1 个元素 >= x，但实际有 0 个。
如果 x = 2，应该有 2 个元素 >= x，但实际有 0 个。
x 不能取更大的值，因为 nums 中只有两个元素。

示例 3：

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

示例 4：

输入：nums = [3,6,7,7,0]
输出：-1

提示：

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

Submission

运行时间: 23 ms

内存: 15.9 MB

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort(reverse=True)
        n = len(nums)
        for i in range(1, n + 1):
            if (nums[i - 1]) >= i and (i == n or nums[i] < i):
                return i
        
        return -1

Explain

首先对数组进行降序排序。然后遍历排序后的数组，检查数组中是否有恰好i个元素大于或等于i。这通过检查排序后在i-1位置的元素是否大于或等于i来进行，同时i位置的元素（如果存在）应小于i，确保恰好有i个元素。如果找到这样的i，则i即为特征值。遍历结束如果没有找到符合条件的i则返回-1。

时间复杂度: O(n log n)

空间复杂度: O(1)

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort(reverse=True)  # 对数组进行降序排序
        n = len(nums)  # 获取数组的长度
        for i in range(1, n + 1):  # 遍历可能的特征值x从1到n
            if (nums[i - 1]) >= i and (i == n or nums[i] < i):  # 检查恰好有i个元素大于或等于i
                return i  # 返回i作为特征值
        return -1  # 如果没有符合条件的i，则返回-1

Explore

在这个问题中，我们需要找到最小的i使得恰好有i个元素大于或等于i。通过降序排序，我们可以直接从数组的开始向后遍历，依次检查每个位置的元素是否满足条件。这样可以在寻找特征值时更直观和简洁地判断恰好有i个元素大于或等于i。如果使用升序排序，则需要从数组的末尾向前遍历，同时计数满足条件的元素数量，这会增加实现的复杂性。

降序排序后的数组中，位于`i-1`位置的元素是第i大的元素。我们的目标是找到最小的i，使得恰好有i个元素大于或等于i。因此，检查`i-1`位置的元素是否大于或等于i可以直接确定是否有i个元素满足条件。这种方法可以避免额外的计数操作，使算法更高效。

当`i`等于数组长度`n`时，`nums[i]`实际上是不存在的，因此不存在`nums[i] < i`的情况。此时，只需要确认数组中所有的`n`个元素都大于或等于`n`即可。如果`nums[n-1]`（即最后一个元素）都大于或等于`n`，则自然所有元素都满足这一条件。

如果数组中所有元素都相等，结果取决于元素的值与数组的长度。例如，对于数组[4,4,4,4]，因为数组长度为4，所有元素都为4，所以数组中恰好有4个元素大于或等于4。因此，输出为4。这种情况下，数组的特征值正好等于数组的长度，因为所有元素都等于这个长度。