ytwzjs烟台网站建设,如何制作自己的公众号,网站安全防护措施,八百客crm管理系统[JavaScript 刷题] 特殊数组的特征值, leetcode 1608
这道题在一个列表上看到的#xff0c;刚开始用暴力解想过了就过了#xff0c;不过后面看了一下关键字#xff0c;发现解法……非常有趣。
时间复杂度可以从 O(n2)O(n^2)O(n2) 降为 O(nlog(n))O(n log(n))O(nlog(n))刚开始用暴力解想过了就过了不过后面看了一下关键字发现解法……非常有趣。
时间复杂度可以从 O(n2)O(n^2)O(n2) 降为 O(nlog(n))O(n log(n))O(nlog(n))再降为 O(n)O(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暴力解的时间复杂度就是 n2n^2n2也就是 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 1717 171 所以继续执行。
当 x 2727 272 所以继续执行。
当 x 3626 262 所以继续执行。
当 x 4343 434已经不满足存在于 x 个数字大于等于 x 本身这一条件因此可以直接返回 −1-1−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))$会比暴力解更加的有效。
二分搜索
二分算法的过程以及原理和排序就有点相似已知结果只可能存在于 1x1001 x 1001x100因此对这个区间进行二分搜索找到出现 x xx 的数字正好出现 xxx 次的这个值。
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−1001 - 1001−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 its frequence, so we can check count directly after adding the frequencycount buckets[i];if (count i) return count;}return -1;
}这里走了两个遍历所以时间复杂度是 O(n)O(n)O(n)应该来说是没办法找到更优的解法了。
