LC 1608. 特殊数组的特征值

题目描述

这是 LeetCode 上的 1608. 特殊数组的特征值 ，难度为 简单。

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

注意： x 不必 是 nums 的中的元素。

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

示例 1：

1
2
3
4
5
输入：nums = [3,5]

输出：2

解释：有 2 个元素（3 和 5）大于或等于 2 。

示例 2：
1
2
3
4
5
6
7
8
9
输入：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
4
5
输入：nums = [0,4,3,0,4]

输出：3

解释：有 3 个元素大于或等于 3 。

示例 4：
1
2
3
输入：nums = [3,6,7,7,0]

输出：-1

提示：

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

排序 + 枚举 + 二分

根据题意并结合 $nums[i]$ 的数据范围为 $1e3$，我们可以通过「枚举」的方式找到 x，而对于每个 x 的合法性检查，我们需要快速知道 nums 中比 x 大的数的个数，这可以通过「排序 + 二分」来做。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
};

  • 时间复杂度：排序的复杂度为 $O(n\log{n})$；枚举找 x 的复杂度为 $O(C\log{n})$，其中 $C = 1e3$ 为 $nums[i]$ 的值域大小
  • 空间复杂度：$O(\log{n})$

排序 + 二分

若不利用 $nums[i]$ 的值域偏小（即值域放大到 $1e9$），我们可以通过「排序 + 两次二分」的操作来做：第一次二分找分割点 x（二分范围为 $[0, 1e9]$）；第二次则是在 getCnt 函数内部中使用二分来对 x 进行合法性检查。

我们知道若真实的特殊值为 x，那么在以 x 为分割点的数轴上具有「二段性」，假设当前值为 k：

  • 小于真实特殊值 x 的 k 值满足「nums 中大于等于 k 的元素个数超过 k 个」
  • 大于等于真实特殊值 x 的 k 值满足「nums 中大于等于 k 的元素个数不超过 k 个」

因此可以通过「二分」来找真实特殊值为 x，至于 x 的合法检查则和解法一相同，先通过排序确保数组有序，再通过二分的方式来统计大于等于 x 的数的个数。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 x) {
        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 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

  • 时间复杂度：排序复杂度为 $O(n\log{n})$，二分找答案复杂度为 $O(\log{C} \times \log{n})$
  • 空间复杂度：$O(\log{n})$

模拟（计数 + 枚举）

另外一种除非过大缩放 $nums$ 的长度 $n$，否则仅有代码量优势的做法是使用「计数 + 枚举」的模拟做法。

先使用静态数组对 $nums$ 进行词频统计，随后通过逆序枚举的方式找特殊值 x，同时使用 tot 统计遍历过的桶的总元素个数，当满足 tot = x 时，返回结果。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
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 代码：
1
2
3
4
5
6
7
8
9
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
};

  • 时间复杂度：$O(n + C)$，其中 $C = 1e3$ 为 $nums[i]$ 的值域大小
  • 空间复杂度：$O(C)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1608 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。