1608. 特殊数组的特征值 :「枚举 + 二分」&「两次二分」&「计数模拟」

我报名参加金石计划一期挑战——瓜分10万奖池，这是我的第10篇文章，点击查看活动详情

题目描述

这是 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 个。
x 不能取更大的值，因为 nums 中只有两个元素。

示例 3：

输入：nums = [0,4,3,0,4]

输出：3

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

示例 4：

输入：nums = [3,6,7,7,0]

输出：-1

提示：

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

排序 + 枚举 + 二分

根据题意并结合 nums[i]nums[i]nums[i] 的数据范围为 1e31e31e3，我们可以通过「枚举」的方式找到 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
};

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

排序 + 二分

若不利用 nums[i]nums[i]nums[i] 的值域偏小（即值域放大到 1e91e91e9），我们可以通过「排序 + 两次二分」的操作来做：第一次二分找分割点 x（二分范围为 [0,1e9][0, 1e9][0,1e9]）；第二次则是在 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 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 代码：

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(nlog⁡n)O(n\log{n})O(nlogn)，二分找答案复杂度为 O(log⁡C×log⁡n)O(\log{C} \times \log{n})O(logC×logn)
• 空间复杂度：O(log⁡n)O(\log{n})O(logn)

模拟（计数 + 枚举）

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

先使用静态数组对 numsnumsnums 进行词频统计，随后通过逆序枚举的方式找特殊值 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
};

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

最后

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

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

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

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉