加载中...
1608-特殊数组的特征值(Special Array With X Elements Greater Than or Equal X)
发表于:2021-12-03 | 分类: 简单
字数统计: 940 | 阅读时长: 4分钟 | 阅读量:

原文链接: https://leetcode-cn.com/problems/special-array-with-x-elements-greater-than-or-equal-x

英文原文

You are given an array nums of non-negative integers. nums is considered special if there exists a number x such that there are exactly x numbers in nums that are greater than or equal to x.

Notice that x does not have to be an element in nums.

Return x if the array is special, otherwise, return -1. It can be proven that if nums is special, the value for x is unique.

 

Example 1:

Input: nums = [3,5]
Output: 2
Explanation: There are 2 values (3 and 5) that are greater than or equal to 2.

Example 2:

Input: nums = [0,0]
Output: -1
Explanation: No numbers fit the criteria for x.
If x = 0, there should be 0 numbers >= x, but there are 2.
If x = 1, there should be 1 number >= x, but there are 0.
If x = 2, there should be 2 numbers >= x, but there are 0.
x cannot be greater since there are only 2 numbers in nums.

Example 3:

Input: nums = [0,4,3,0,4]
Output: 3
Explanation: There are 3 values that are greater than or equal to 3.

Example 4:

Input: nums = [3,6,7,7,0]
Output: -1

 

Constraints:

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

中文题目

给你一个非负整数数组 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

通过代码

高赞题解

本场周赛题解 | 我的LeetCode比赛题解

方法一:暴力枚举特征值

枚举所有可能的特征值(最大为$N$),判断是否成立。

时间复杂度$O(N^2)$。

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

方法二:排序+枚举特征值

先排序,然后枚举特征值,这样可以快速找到符合每个特征值的元素个数。

时间复杂度$O(N\log N)$。

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

方法三:计数数组后缀和

我们可以首先进行计数($\geq N$的元素视为$N$,因为特征值最大为$N$),然后计算计数数组的后缀和,就可以直接得到不小于某一个数的元素个数。

时间复杂度$O(N)$。

class Solution {
public:
    int specialArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> cnt(n + 1);
        for (int num : nums)
            cnt[min(num, n)]++;
        for (int i = n; i >= 0; --i) {
            if (i < n)
                cnt[i] += cnt[i + 1];
            if (cnt[i] == i)
                return i;
        }
        return -1;
    }
};

统计信息

通过次数 提交次数 AC比率
10366 16228 63.9%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
1622-奇妙序列(Fancy Sequence)
下一篇:
1609-奇偶树(Even Odd Tree)
本文目录
本文目录