题目描述
这是 LeetCode 上的 1608. 特殊数组的特征值 ，难度为 简单。
Tag : 「排序」、「二分」、「枚举」、「模拟」、「计数」
给你一个非负整数数组
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 示例 3：
输入：nums = [0,4,3,0,4]
输出：3
解释：有 3 个元素大于或等于 3 。 示例 4：
输入：nums = [3,6,7,7,0]
输出：-1 提示：
排序 + 枚举 + 二分
根据题意并结合 的数据范围为 ，我们可以通过「枚举」的方式找到
x
，而对于每个
x
的合法性检查，我们需要快速知道
nums
中比
x
大的数的个数，这可以通过「排序 + 二分」来做。
Java 代码：
class Solution {
public int specialArray(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
for (int x = 0; x < 1010; x++) {
int l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= x) r = mid;
else l = mid + 1;
}
if (nums[r] >= x && x == n - r) return x;
}
return -1;
}
} TypeScript 代码：
function specialArray(nums: number[]): number {
const n = nums.length
nums.sort((a,b)=>a-b)
for (let x = 0; x < 1010; x++) {
let l = 0, r = n - 1
while (l < r) {
const mid = l + r >> 1
if (nums[mid] >= x) r = mid
else l = mid + 1
}
if (nums[r] >= x && x == n - r) return x
}
return -1 - 时间复杂度：排序的复杂度为；枚举找
x
- 空间复杂度：
排序 + 二分
若不利用 的值域偏小（即值域放大到 ），我们可以通过「排序 + 两次二分」的操作来做：第一次二分找分割点
x
（二分范围为 ）；第二次则是在
getCnt
函数内部中使用二分来对
x
进行合法性检查。
我们知道若真实的特殊值为
x
，那么在以
x
为分割点的数轴上具有「二段性」，假设当前值为
k
：
- 小于真实特殊值
x
k
nums
k
k
- 大于等于真实特殊值
x
k
nums
k
k
因此可以通过「二分」来找真实特殊值为
x
，至于
x
的合法检查则和解法一相同，先通过排序确保数组有序，再通过二分的方式来统计大于等于
x
的数的个数。
Java 代码：
class Solution {
int[] nums;
public int specialArray(int[] _nums) {
nums = _nums;
Arrays.sort(nums);
int l = 0, r = (int) 1e9;
while (l < r) {
int mid = l + r >> 1;
if (getCnt(mid) <= mid) r = mid;
else l = mid + 1;
}
return getCnt(r) == r ? r : -1;
}
int getCnt(int {
int n = nums.length, l = 0, r = n - 1;
while (l < r) {
int mid = l + r >> 1;
if (nums[mid] >= x) r = mid;
else l = mid + 1;
}
return nums[r] >= x ? n - r : 0;
}
} TypeScript 代码：
let nums: number[]
function specialArray(_nums: number[]): number {
nums = _nums
nums.sort((a,b)=>a-b)
let l = 0, r = 1e9
while (l < r) {
const mid = l + r >> 1
if (getCnt(mid) <= mid) r = mid
else l = mid + 1
}
return getCnt(r) == r ? r : -1
};
function getCnt(x: number): number {
let n = nums.length, l = 0, r = n - 1
while (l < r) {
const mid = l + r >> 1
if (nums[mid] >= x) r = mid
else l = mid + 1
}
return nums[r] >= x ? n - r : 0 - 时间复杂度：排序复杂度为，二分找答案复杂度为
- 空间复杂度：
模拟（计数 + 枚举）
另外一种除非过大缩放 的长度 ，否则仅有代码量优势的做法是使用「计数 + 枚举」的模拟做法。
先使用静态数组对 进行词频统计，随后通过逆序枚举的方式找特殊值
x
，同时使用
tot
统计遍历过的桶的总元素个数，当满足
tot = x
时，返回结果。
Java 代码：
class Solution {
public int specialArray(int[] nums) {
int[] cnts = new int[1010];
for (int x : nums) cnts[x]++;
for (int i = 1009, tot = 0; i >= 0; i--) {
tot += cnts[i];
if (i == tot) return i;
}
return -1;
}
} TypeScript 代码：
function specialArray(nums: number[]): number {
const cnts = new Array<number>(1010).fill(0)
for (let x of nums) cnts[x]++
for (let i = 1009, tot = 0; i >= 0; i--) {
tot += cnts[i]
if (tot == i) return i
}
return -1 - 时间复杂度：，其中为
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第
No.1608
篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
![Java String.format方法的简单使用[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)