LeetCode 题解工作台
特殊数组的特征值
给你一个非负整数数组 nums 。如果存在一个数 x ，使得 nums 中恰好有 x 个元素 大于或者等于 x ，那么就称 nums 是一个 特殊数组 ，而 x 是该数组的 特征值 。 注意： x 不必 是 nums 的中的元素。 如果数组 nums 是一个 特殊数组 ，请返回它的特征值 x 。否则…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·搜索·答案·空间
答案摘要
我们在 范围内枚举 ，然后统计数组中大于等于 的元素个数，记为 。若存在 与 相等，直接返回 。 时间复杂度 ，其中 是数组的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
给你一个非负整数数组 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 <= 1000 <= nums[i] <= 1000
解题思路
方法一：暴力枚举
我们在 范围内枚举 ，然后统计数组中大于等于 的元素个数，记为 。若存在 与 相等，直接返回 。
时间复杂度 ，其中 是数组的长度。空间复杂度 。
class Solution:
def specialArray(self, nums: List[int]) -> int:
for x in range(1, len(nums) + 1):
cnt = sum(v >= x for v in nums)
if cnt == x:
return x
return -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Check if candidate x can exceed array length.
- question_mark
Watch out for off-by-one errors when counting >= x.
- question_mark
Consider using sorting to simplify counting elements efficiently.
常见陷阱
外企场景- error
Assuming x must be an element of nums instead of any integer in [0, nums.length].
- error
Miscounting elements equal to x, leading to incorrect results.
- error
Ignoring edge cases where all elements are zeros or duplicates.
进阶变体
外企场景- arrow_right_alt
Find x where at least x elements are greater than or equal to x.
- arrow_right_alt
Return all possible x values instead of a unique one.
- arrow_right_alt
Apply the pattern to multidimensional arrays counting elements in each row.