『LeetCode』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\) 的取值最大不超过数组的长度，所以枚举所有可能是一种最简单粗暴的办法。

# Code language: Python
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        for x in range(len(nums) + 1):
            if sum(a >= x for a in nums) == x:
                return x
        return -1

// Code language: Java
class Solution {
    public int specialArray(int[] nums) {
        for (int x = 1, n = nums.length; x <= n; ++x) {
            int cnt = 0;
            for (int a: nums) {
                if (a >= x && ++cnt > x) break; 
            }
            if (x == cnt) return x;
        }
        return -1;
    }
}

// Code language: C++
class Solution {
public:
    int specialArray(vector<int>& nums) {
        for (int x = 1, n = nums.size(); x <= n; ++x) {
            int cnt = 0;
            for (int a: nums) {
                if (a >= x && ++cnt > x) break; 
            }
            if (x == cnt) return x;
        }
        return -1;
    }
};

/* Code language: JavaScript */
/**
 * @param {number[]} nums
 * @return {number}
 */
var specialArray = function(nums) {
    for (let x = 1, n = nums.length; x <= n; ++x) {
        let cnt = 0;
        for (const a of nums) {
            if (a >= x && ++cnt > x) break; 
        }
        if (x == cnt) return x;
    }
    return -1;
};

时间复杂度: \(O(n^2)\)
空间复杂度: \(O(1)\)

二分查找

注意到上一种方法的瓶颈主要在于检查多少个元素大于等于 \(x\)，不难想到可以先对数组排序再使用二分查找进行优化。

更近一步优化的方法是，对于数组中大于 \(x\) 的数量显然是与 \(x\) 呈负相关的，\(x\) 越大，满足条件的数值数量越小，所以对于 \(x\) 也可以使用二分查找，将查找的复杂度由 \(n \log n\) 降低到 \((\log n)^2\), 但实际上此时时间复杂度瓶颈已经转移到排序操作上了，所以该优化并不会降低总体的时间复杂度上界。

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

# Code language: Python
class Solution:
    def specialArray(self, nums: List[int]) -> int:
        n = len(nums)
        nums.sort()
        left, right = -1, n + 1
        while left <= right:
            mid = (left + right) >> 1
            if (t := n - bisect.bisect_left(nums, mid)) == mid:
                return mid
            elif t < mid:
                right = mid - 1
            else:
                left = mid + 1
        return -1

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

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

时间复杂度: \(O(n \log n)\)
空间复杂度: \(O(\log n)\), 视排序算法而定

如果对你有帮助的话，请给我点个赞吧~

欢迎前往我的博客或 Algorithm - Github 查看更多题解

小鲸鱼的梦境

『LeetCode』1608 特殊数组的特征值

题目

标签

题解

枚举

二分查找