跳至主要內容

1608. 特殊数组的特征值


1608. 特殊数组的特征值

🟢   🔖  数组 二分查找 排序  🔗 力扣open in new window LeetCodeopen in new window

题目

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),没有使用额外的空间。

代码

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