题目描述
给你一个非负整数数组 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
解法
方法一：暴力枚举
我们在 $[1..n]$ 范围内枚举 $x$，然后统计数组中大于等于 $x$ 的元素个数，记为 $cnt$。若存在 $cnt$ 与 $x$ 相等，直接返回 $x$。
时间复杂度 $O(n^2)$，其中 $n$ 是数组的长度。空间复杂度 $O(1)$。
方法二：排序 + 二分查找
我们也可以先对 nums 进行排序。
接下来同样枚举 $x$，利用二分查找，找到 nums 中第一个大于等于 $x$ 的元素，快速统计出 nums 中大于等于 $x$ 的元素个数。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 是数组的长度。
| class Solution:
def specialArray(self, nums: List[int]) -> int:
nums.sort()
n = len(nums)
for x in range(1, n + 1):
cnt = n - bisect_left(nums, x)
if cnt == x:
return x
return -1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int specialArray(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int x = 1; x <= n; ++x) {
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
int cnt = n - left;
if (cnt == x) {
return x;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution {
public:
int specialArray(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
for (int x = 1; x <= n; ++x) {
int cnt = n - (lower_bound(nums.begin(), nums.end(), x) - nums.begin());
if (cnt == x) return x;
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | func specialArray(nums []int) int {
sort.Ints(nums)
n := len(nums)
for x := 1; x <= n; x++ {
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if nums[mid] >= x {
right = mid
} else {
left = mid + 1
}
}
cnt := n - left
if cnt == x {
return x
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | function specialArray(nums: number[]): number {
const n = nums.length;
let left = 0;
let right = n + 1;
while (left < right) {
const mid = (left + right) >> 1;
const count = nums.reduce((r, v) => r + (v >= mid ? 1 : 0), 0);
if (count === mid) {
return mid;
}
if (count > mid) {
left = mid + 1;
} else {
right = mid;
}
}
return -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | use std::cmp::Ordering;
impl Solution {
pub fn special_array(nums: Vec<i32>) -> i32 {
let n = nums.len() as i32;
let mut left = 0;
let mut right = n + 1;
while left < right {
let mid = left + (right - left) / 2;
let mut count = 0;
for &num in nums.iter() {
if num >= mid {
count += 1;
}
}
match count.cmp(&mid) {
Ordering::Equal => {
return mid;
}
Ordering::Less => {
right = mid;
}
Ordering::Greater => {
left = mid + 1;
}
}
}
-1
}
}
|