原文链接: 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
通过代码
高赞题解
方法一:暴力枚举特征值
枚举所有可能的特征值(最大为$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% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|