题目描述

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

注意: x 不必nums 的中的元素。

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

示例 1:

1
2
3
输入:nums = [3,5]
输出:2
解释:有 2 个元素(3 和 5)大于或等于 2 。

示例 2:

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

示例 3:

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

示例 4:

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

提示:

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

来源:力扣(LeetCode)

题解

SpecialArrayWithXElementsGreaterThanOrEqualX

排序 + 一次遍历

1
2
3
4
5
6
7
8
9
10
11
12
public int specialArray(int[] nums) {
Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {
int x = nums.length - i;
if (nums[i] >= x && (i == 0 || x > nums[i - 1])) {
return x;
}
}

return -1;
}
  • 时间复杂度: O(nlogn)*,其中 *n 是数组 nums 的长度
  • 空间复杂度: *O(logn)*,即为排序需要的栈空间

submissions-2022091301

排序 + 枚举 + 二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int specialArray(int[] nums) {
Arrays.sort(nums);

// 枚举 x
for (int i = 0; i < 1010; i++) {
// 二分查找 x 在排序后数组中的位置
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left >> 1);
if (nums[mid] < i) left = mid + 1;
else right = mid;
}
// 必须添加 nums[left] >= i 条件.
// 举例 [0, 0] 当 x = 1 时, 二分查找比 1 大的数组元素的位置, 二分查找的结果 left = 1.
// 因为没有更多更大的元素可以查找. 此时的结果是不满足 nums[left] > i 的情况的.
if (nums[left] >= i && i == (nums.length - left)) return i;
}

return -1;
}
  • 时间复杂度: 排序的复杂度为 *O(nlogn)*;枚举找 x 的复杂度为 *O(Clogn)*,其中 C = 1e3 为 nums[i] 的值域大小
  • 空间复杂度: O(logn)

submissions-2022091302

排序 + 二分

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
30
31
32
public int specialArray(int[] nums) {
// 只是将枚举过程优化了, 如果大于等于 x 的元素有 n 个且 n > x, 那么我们需要让 x 变大 n 变小, 从而寻找 x == n 的情况.
Arrays.sort(nums);

// 二分查找
int left = 0;
int right = 1010;
while (left < right) {
// 这里无论是哪种二分查找模板都没关系, 因为最终只要 count == mid 的情况
int mid = left + (right - left >> 1);
int count = this.countNums(nums, mid);
if (count > mid){
left = mid + 1;
} else {
right = mid;
}
}

return this.countNums(nums, left) == left ? left : -1;
}

private int countNums(int[] nums, int x) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left >> 1);
if (nums[mid] < x) left = mid + 1;
else right = mid;
}
if (nums[left] >= x) return nums.length - left;
return 0;
}
  • 时间复杂度: 排序复杂度为 O(nlogn)*,二分查找复杂度为 *O(logC × logn)
  • 空间复杂度: O(logn)

submissions-2022091303

模拟(计数 + 枚举)

1
2
3
4
5
6
7
8
9
10
11
12
public int specialArray(int[] nums) {
// 统计每个数字出现的次数
int[] countArr = new int[1010];
for (int num : nums) countArr[num]++;
// 枚举 x
for (int i = 1009, count = 0; i >=0 ; i--) {
// 如果 nums[i] 大于 x, 那么 nums[i + 1] 也一定大于
count += countArr[i];
if (count == i) return i;
}
return -1;
}
  • 时间复杂度: O(nlogn)*,其中 *n 是数组 nums 的长度
  • 空间复杂度: O(C)

submissions-2022091304

参考资料

__END__