[JavaScript 刷题] 特殊数组的特征值, leetcode 1608

这道题在一个列表上看到的，刚开始用暴力解想过了就过了，不过后面看了一下关键字，发现解法……非常有趣。

时间复杂度可以从 $O(n^2)$ 降为 $O(nlog(n))$，再降为 $O(n)$，顺便记一下学习过程，毕竟很少看到简单题这么复杂的。

题目

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.

解题思路

暴力解

题意问的是是否存在特殊数字 x，使得数组中出现大于等于 x 的数字正好等同鱼 x 本身。假设数组中所有的数字都比 x 大，那么最多存在 nums.length 个数字，反之则是 0。

这道题给的上限是 1 <= nums.length <= 100，也就是说 x 的上限为 100，暴力解的时间复杂度就是 $n^2$，也就是 10000，所以不会超时（甚至还没一些题目的 input 多）。

暴力解的做法就是遍历两次数组，每次便利的时候记录大于等于当前值 i 出现的次数，如果计算出来正好等于 i，则可以直接返回当前 i，解法如下：

function specialArray(nums: number[]): number {for (let i = 1; i <= nums.length; i++) {let counter = 0;for (let j = 0; j < nums.length; j++) {console.log(nums[j], counter);if (nums[j] >= i) counter++;if (counter > i) break;}if (counter === i) return i;}return -1;
}

排序

另一种思路是排序去做，排序完了之后只需要从大到小找比当前的 i 大的数字出现的次数即可。

以 [3,6,7,7,0] 为例，排序后的结果为 [7, 7, 6, 3, 0]。

当 x = 1，$7>1$ 所以继续执行。

当 x = 2，$7>2$ 所以继续执行。

当 x = 3，$6>2$ 所以继续执行。

当 x = 4，$3<4$，已经不满足存在于 x 个数字大于等于 x 本身这一条件，因此可以直接返回 $-1$。

解法如下：

function specialArray(nums: number[]): number {nums.sort((a, b) => b - a);let x: number = -1;for (let i = 1; i <= nums.length; i++) {if (nums[i - 1] >= i) {x = i;continue;}if (nums[i - 1] >= x) return -1;}return x;
}

这样的解法时间复杂度为 $ O(nlog(n))$，会比暴力解更加的有效。

二分搜索

二分算法的过程以及原理和排序就有点相似，已知结果只可能存在于 $1<=x<=100$，因此对这个区间进行二分搜索，找到出现 $>=x$ 的数字正好出现 $x$ 次的这个值。

function specialArray(nums: number[]): number {let left = 1,right = nums.length;while (left <= right) {const mid = Math.floor((left + right) / 2);const count = nums.reduce((accum, curr) => (mid <= curr ? accum + 1 : accum),0);if (count === mid) return mid;if (count > mid) left = mid + 1;else right = mid - 1;}// need to check when left is also a posible solutionconst count = nums.reduce((accum, curr) => (left <= curr ? accum + 1 : accum),0);return count === left ? left : -1;
}

虽然也是 $ O(nlog(n))$，不过二分算法少走了一个遍历，因此速度相比较而言会快一些($left <= nums.length$ 是肯定的)，不过大 O 都一样。

桶排序

桶排序利用的是所有的数字都可能会被归类到 $1-100$ 的这个容器中，将所有的数字全都归类到对应的桶里进行倒叙的频率检查，最后找到符合条件的特殊数字即可。

function specialArray(nums: number[]): number {const length = nums.length;const buckets = new Array(length + 1).fill(0);for (const num of nums) {buckets[Math.min(num, length)] += 1;}let count = 0;for (let i = length; i > 0; i--) {// since it's frequence, so we can check count directly after adding the frequencycount += buckets[i];if (count === i) return count;}return -1;
}

这里走了两个遍历，所以时间复杂度是 $O(n)$，应该来说是没办法找到更优的解法了。