宫水三叶的刷题日记

V1

2022/09/12阅读:7主题:前端之巅同款

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

题目描述

这是 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

提示:

排序 + 枚举 + 二分

根据题意并结合 的数据范围为 ,我们可以通过「枚举」的方式找到 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

  • 小于真实特殊值 xk 值满足「nums 中大于等于 k 的元素个数超过 k 个」
  • 大于等于真实特殊值 xk 值满足「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 = (int1e9;
        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
}
  • 时间复杂度:排序复杂度为 ,二分找答案复杂度为
  • 空间复杂度:

模拟(计数 + 枚举)

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

先使用静态数组对 进行词频统计,随后通过逆序枚举的方式找特殊值 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 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

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

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

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

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

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1