1608.md

title	description	keywords
1608. 特殊数组的特征值	LeetCode 1608. 特殊数组的特征值题解，Special Array With X Elements Greater Than or Equal X，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1608. 特殊数组的特征值 特殊数组的特征值 Special Array With X Elements Greater Than or Equal X 解题思路 数组 二分查找 排序

1608. 特殊数组的特征值

🟢 Easy  🔖  数组 二分查找 排序  🔗 力扣 LeetCode

题目

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

解题思路

思路一：前缀数组

可以通过前缀数组统计每个数值的出现频率，再从后向前累积计算大于等于当前值的数字个数，这样避免了直接对数组进行排序，提升效率。

1. 统计频率：

   创建一个大小为 n + 1 的频次数组 freq，其中 freq[i] 表示值为 i 的数字在数组中出现的次数。

   如果某个数字大于数组长度 n，我们将它归入 freq[n]，因为超过 n 的数字对结果的判断没有影响。

2. 累积计数：

   从后往前开始遍历频次数组 freq，累积计算大于等于当前值的数字个数。

   如果累积个数与当前值相等，则找到了满足条件的 x，直接返回。

3. 返回结果：

   如果遍历结束仍未找到满足条件的值，返回 -1。

复杂度分析

• 时间复杂度： O(n)
  • 频率统计：O(n)，遍历数组一次。
  • 累积计数：O(n)，遍历频次数组一次。
  • 总体复杂度为 O(n)。
• 空间复杂度： O(n)
  • 使用一个大小为 n + 1 的频次数组 freq 。

---

思路二：二分查找

1. 排序数组：
   首先对数组 nums 排序，以便可以利用其有序性。

2. 二分查找：
   在 [0, n] 范围内进行二分查找，因为大于等于 x 的元素个数不可能超过数组长度：

   • 对于中间值 mid，计算数组中大于等于 mid 的元素个数 count。
   • 如果 count 恰好等于 mid，返回结果。
   • 如果 count 大于 mid，搜索右半部分；否则搜索左半部分。

3. 计算大于等于 x 的元素个数：

   • 定义一个辅助函数 getGreaterOrEqualCount，用来计算，数组中大于等于 x 的元素个数。
   • 依然可以通过 二分查找 来快速找到数组中第一个大于等于 x 的位置 index。
   • 返回大于等于 x 的元素个数：n - index。

4. 验证 x 是否满足条件：
   如果 x == n - index，则 x 是特殊值；否则继续调整 x 的范围。

复杂度分析

• 时间复杂度：O(n log n)，

  1. 排序：O(n log n)。

  2. 二分查找：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) 的复杂度。

  3. 总复杂度：O(n log n) + O(log^2 n)，排序是主导因素，整体复杂度为 O(n log n)。

• 空间复杂度：O(1)，没有使用额外的空间。

代码

::: code-tabs @tab 前缀数组

/**
 * @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; // 没有找到符合条件的值
};

@tab 二分查找

/**
 * @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;
}

:::