检查整数及其两倍数是否存在
二分搜索
-
解题思路：
- 第一层循环确定一个 N；
- 第二层循环二分查找 M；
-
复杂度：
- 时间复杂度：O(nlogn)，排序的时间复杂度为 O(nlogn)，两次指针遍历的过程时间复杂度为 O(n)，综合起来，复杂度为 O(nlogn)；
- 空间复杂度：O(1)；
-
代码实现：
function checkIfExist(arr) { arr.sort((a, b) => (a - b)) for (let i = 0; i < arr.length; i++) { let left = 0 let right = arr.length - 1; while (left <= right) { let mid = left + (right - left) >> 1; if (arr[mid] * 2 < arr[i]) left = mid + 1 else right = mid - 1; } if (arr[left] * 2 === arr[i] && left !== i) return true } return false };
哈希
-
解题思路：
- 利用 「两数之和」 hash 的解法；
- 循环当前数组，将当前元素存入 hash，每次放入之前都会判断当前元素的二倍或当前元素的一半是否存在 hash 中；
-
复杂度：
- 时间复杂度：O(n)，哈希表的查询时间复杂度为 O(1)，查询次数为 O(n)，综合起来，时间复杂度为 O(n)；
- 空间复杂度：O(n)，哈希表最多需要存储 n 个元素；
-
代码实现：
var checkIfExist = function (arr) { let set = new Set(); for (let i = 0; i < arr.length; i++) { if (set.has(arr[i] * 2) || (arr[i] % 2 === 0 && set.has(arr[i] / 2))) return true; set.add(arr[i]); } return false; }
打赏作者
您的打赏是我前进的动力
微信
支付宝
1356.根据数字二进制下 1 的数目排序
上一篇
评论
