Description#
You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.
Notice that x does not have to be an element in nums.
Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.
Example 1:
Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.
Example 2:
Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.
Example 3:
Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 1000
Solutions#
Solution 1#
1
2
3
4
5
6
7
| 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int specialArray(int[] nums) {
for (int x = 1; x <= nums.length; ++x) {
int cnt = 0;
for (int v : nums) {
if (v >= x) {
++cnt;
}
}
if (cnt == x) {
return x;
}
}
return -1;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int specialArray(vector<int>& nums) {
for (int x = 1; x <= nums.size(); ++x) {
int cnt = 0;
for (int v : nums) cnt += v >= x;
if (cnt == x) return x;
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| func specialArray(nums []int) int {
for x := 1; x <= len(nums); x++ {
cnt := 0
for _, v := range nums {
if v >= x {
cnt++
}
}
if cnt == x {
return x
}
}
return -1
}
|
1
2
3
4
5
6
7
8
9
| function specialArray(nums: number[]): number {
const n = nums.length;
for (let i = 0; i <= n; i++) {
if (i === nums.reduce((r, v) => r + (v >= i ? 1 : 0), 0)) {
return i;
}
}
return -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| impl Solution {
pub fn special_array(nums: Vec<i32>) -> i32 {
let n = nums.len() as i32;
for i in 0..=n {
let mut count = 0;
for &num in nums.iter() {
if num >= i {
count += 1;
}
}
if count == i {
return i;
}
}
-1
}
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
| 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
}
}
|
