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 <= 1000 <= 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 <= 1000 <= 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;
}