1608. 特殊数组的特征值
1608. 特殊数组的特征值
题目
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.
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 + 1
的频次数组freq
,其中freq[i]
表示值为i
的数字在数组中出现的次数。如果某个数字大于数组长度
n
,我们将它归入freq[n]
,因为超过n
的数字对结果的判断没有影响。累积计数:
从后往前开始遍历频次数组
freq
,累积计算大于等于当前值的数字个数。如果累积个数与当前值相等,则找到了满足条件的
x
,直接返回。返回结果:
如果遍历结束仍未找到满足条件的值,返回
-1
。
复杂度分析
- 时间复杂度:
O(n)
- 频率统计:
O(n)
,遍历数组一次。 - 累积计数:
O(n)
,遍历频次数组一次。 - 总体复杂度为
O(n)
。
- 频率统计:
- 空间复杂度:
O(n)
- 使用一个大小为
n + 1
的频次数组freq
。
- 使用一个大小为
思路二:二分查找
排序数组:
首先对数组nums
排序,以便可以利用其有序性。二分查找:
在[0, n]
范围内进行二分查找,因为大于等于x
的元素个数不可能超过数组长度:- 对于中间值
mid
,计算数组中大于等于mid
的元素个数count
。 - 如果
count
恰好等于mid
,返回结果。 - 如果
count
大于mid
,搜索右半部分;否则搜索左半部分。
- 对于中间值
计算大于等于
x
的元素个数:- 定义一个辅助函数
getGreaterOrEqualCount
,用来计算,数组中大于等于x
的元素个数。 - 依然可以通过 二分查找 来快速找到数组中第一个大于等于
x
的位置index
。 - 返回大于等于
x
的元素个数:n - index
。
- 定义一个辅助函数
验证
x
是否满足条件:
如果x == n - index
,则x
是特殊值;否则继续调整x
的范围。
复杂度分析
时间复杂度:
O(n log n)
,排序:
O(n log n)
。二分查找:
O(log n) * O(log n)
- 主函数中,
x
的范围是[0, n]
,进行二分查找需要O(log n)
。 - 每次验证候选值
x
,需要通过getGreaterOrEqualCount
计算大于等于x
的元素个数,也用二分查找实现,复杂度为O(log n)
。 - 总共需要
O(log n) * O(log n) = O(log^2 n)
的复杂度。
- 主函数中,
总复杂度:
O(n log n) + O(log^2 n)
,排序是主导因素,整体复杂度为O(n log n)
。
空间复杂度:
O(1)
,没有使用额外的空间。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var specialArray = function (nums) {
const n = nums.length;
let freq = new Array(n + 1).fill(0);
// 统计频率
for (let num of nums) {
freq[Math.min(n, num)]++;
}
// 从后向前累积计数
let count = 0;
for (let i = n; i >= 1; i--) {
count += freq[i];
if (i === count) return i; // 找到满足条件的 x
}
return -1; // 没有找到符合条件的值
};
/**
* @param {number[]} nums
* @return {number}
*/
var specialArray = function (nums) {
nums.sort((a, b) => a - b); // 排序数组
const n = nums.length;
let left = 0,
right = n; // 二分查找的范围 [0, n]
while (left <= right) {
const mid = Math.floor((left + right) / 2);
const count = getGreaterOrEqualCount(nums, mid); // 计算大于等于 mid 的元素个数
if (count === mid) {
return mid; // 找到满足条件的特殊值
} else if (count > mid) {
left = mid + 1; // 说明 mid 太小,继续向右找
} else {
right = mid - 1; // 说明 mid 太大,继续向左找
}
}
return -1; // 如果找不到特殊值,返回 -1
};
/**
* 计算数组中大于等于 x 的元素个数
* @param {number[]} nums
* @param {number} x
* @return {number}
*/
function getGreaterOrEqualCount(nums, x) {
let left = 0,
right = nums.length - 1;
// 找到第一个大于等于 x 的位置
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] >= x) {
right = mid - 1; // 向左缩小范围
} else {
left = mid + 1; // 向右缩小范围
}
}
// 大于等于 x 的元素个数为 n - left
return nums.length - left;
}