1608. 特殊数组的特征值

题目描述

给你一个非负整数数组 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 <= 100
0 <= nums[i] <= 1000

解法

方法一：暴力枚举

思考

特数 \(x\) 只能落在 \([1,n]\)，而 \(n \le 100\)，对每个候选 \(x\) 扫描数组统计 \(\ge x\) 的个数即可在 \(O(n^2)\) 内判定。

若不存在这样的 \(x\)，按题意返回 \(-1\)。

实现上直接枚举 \(x\)，用一次线性计数比较是否等于 \(x\)。

我们在 \([1..n]\) 范围内枚举 \(x\)，然后统计数组中大于等于 \(x\) 的元素个数，记为 \(cnt\)。若存在 \(cnt\) 与 \(x\) 相等，直接返回 \(x\)。

时间复杂度 \(O(n^2)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for x in range(1, len(nums) + 1):
            cnt = sum(v >= x for v in nums)
            if cnt == x:
                return x
        return -1

class Solution {
    public int specialArray(int[] nums) {
        for (int x = 1; x <= nums.length; ++x) {
            int cnt = 0;
            for (int v : nums) {
                if (v >= x) {
                    ++cnt;
                }
            }
            if (cnt == x) {
                return x;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int specialArray(vector<int>& nums) {
        for (int x = 1; x <= nums.size(); ++x) {
            int cnt = 0;
            for (int v : nums) cnt += v >= x;
            if (cnt == x) return x;
        }
        return -1;
    }
};

func specialArray(nums []int) int {
    for x := 1; x <= len(nums); x++ {
        cnt := 0
        for _, v := range nums {
            if v >= x {
                cnt++
            }
        }
        if cnt == x {
            return x
        }
    }
    return -1
}

function specialArray(nums: number[]): number {
    const n = nums.length;
    for (let i = 0; i <= n; i++) {
        if (i === nums.reduce((r, v) => r + (v >= i ? 1 : 0), 0)) {
            return i;
        }
    }
    return -1;
}

impl Solution {
    pub fn special_array(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        for i in 0..=n {
            let mut count = 0;
            for &num in nums.iter() {
                if num >= i {
                    count += 1;
                }
            }
            if count == i {
                return i;
            }
        }
        -1
    }
}

方法二：排序 + 二分查找

思考

方法一对每个 \(x\) 都整表扫描。排序之后，\(\ge x\) 的个数等于 \(n\) 减去第一个不小于 \(x\) 的下标，可用二分在 \(O(\log n)\) 内求得。

总复杂度降为 \(O(n \log n)\)，在 \(n\) 更大时更稳妥，本题规模下两者均可通过。

我们也可以先对 nums 进行排序。

接下来同样枚举 \(x\)，利用二分查找，找到 nums 中第一个大于等于 \(x\) 的元素，快速统计出 nums 中大于等于 \(x\) 的元素个数。

时间复杂度 \(O(n \times \log n)\)，空间复杂度 \(O(\log n)\)。其中 \(n\) 是数组的长度。

Python3JavaC++GoTypeScriptRust

class Solution:
    def specialArray(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        for x in range(1, n + 1):
            cnt = n - bisect_left(nums, x)
            if cnt == x:
                return x
        return -1

class Solution {
    public int specialArray(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int x = 1; x <= n; ++x) {
            int left = 0, right = n;
            while (left < right) {
                int mid = (left + right) >> 1;
                if (nums[mid] >= x) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            int cnt = n - left;
            if (cnt == x) {
                return x;
            }
        }
        return -1;
    }
}

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        for (int x = 1; x <= n; ++x) {
            int cnt = n - (lower_bound(nums.begin(), nums.end(), x) - nums.begin());
            if (cnt == x) return x;
        }
        return -1;
    }
};

func specialArray(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    for x := 1; x <= n; x++ {
        left, right := 0, n
        for left < right {
            mid := (left + right) >> 1
            if nums[mid] >= x {
                right = mid
            } else {
                left = mid + 1
            }
        }
        cnt := n - left
        if cnt == x {
            return x
        }
    }
    return -1
}

function specialArray(nums: number[]): number {
    const n = nums.length;
    let left = 0;
    let right = n + 1;
    while (left < right) {
        const mid = (left + right) >> 1;
        const count = nums.reduce((r, v) => r + (v >= mid ? 1 : 0), 0);

        if (count === mid) {
            return mid;
        }

        if (count > mid) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return -1;
}

use std::cmp::Ordering;
impl Solution {
    pub fn special_array(nums: Vec<i32>) -> i32 {
        let n = nums.len() as i32;
        let mut left = 0;
        let mut right = n + 1;
        while left < right {
            let mid = left + (right - left) / 2;
            let mut count = 0;
            for &num in nums.iter() {
                if num >= mid {
                    count += 1;
                }
            }
            match count.cmp(&mid) {
                Ordering::Equal => {
                    return mid;
                }
                Ordering::Less => {
                    right = mid;
                }
                Ordering::Greater => {
                    left = mid + 1;
                }
            }
        }
        -1
    }
}

1608. 特殊数组的特征值

题目描述

解法

方法一：暴力枚举

方法二：排序 + 二分查找

评论