剑指Offer JavaScript-查找专题

剑指Offer JavaScript-查找专题

Tags
二分查找
CreatedTime
Aug 16, 2022 02:16 AM
Slug
2019-06-23-find-min-num
UpdatedTime
Last updated August 17, 2022

旋转数组最小的数字

1. 题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为 1。

2. 解题思路

最简单的肯定是从头到尾遍历,复杂度是 $O(N)$。这种方法没有利用“旋转数组”的特性
借助二分查找的思想,时间复杂度可以降低到 $O(log(N))$。
可以通过以下方法确定最小值元素的位置,然后移动指针,缩小范围:
  • 中间指针对应的元素 ≥ 左侧元素, 那么中间元素位于原递增数组中, 最小值在右侧
  • 中间指针对应的元素 ≤ 右侧元素, 那么中间元素位于被移动的递增数组中,最小值在左侧
特殊情况,如果三者相等,那么无法判断最小值元素的位置,就退化为普通遍历即可。

3. 代码

先上一段二分查找和实现思路:
/** * 二分查找 * @param {Array} arr * @param {*} elem */ function binarySearch(arr, elem) { let left = 0, right = arr.length - 1, mid = -1; while (left <= right) { // 注意是≤:考虑只剩1个元素的情况 mid = Math.floor((left + right) / 2); if (arr[mid] === elem) { return true; } if (elem < arr[mid]) { right = mid - 1; } else { left = mid + 1; } } return false; } /** * 测试代码 */ console.log(binarySearch([1, 2], 2)); console.log(binarySearch([1, 2], -1)); console.log(binarySearch([1, 2, 10], 2));
借助二分查找的思想,写出本题代码:
/** * 在arr[left, right]中顺序查找最小值 * @param {Array} arr * @param {Number} left * @param {Number} right */ function orderSearchMin(arr, left, right) { let min = arr[left]; for (let i = left + 1; i <= right; ++i) { arr[i] < min && (min = arr[i]); } return min; } /** * 在旋转数组arr中用二分法查找最小值 * @param {Array} arr */ function binSearchMin(arr) { if (!Array.isArray(arr) || !arr.length) { throw Error("Empty Array"); } let left = 0, right = arr.length - 1, mid = null; while (left < right) { if (right === 1 + left) { return arr[right]; } mid = Math.floor((left + right) / 2); if (arr[mid] === arr[left] && arr[mid] === arr[right]) { // 无法判断最小值位置 return orderSearchMin(arr, left, right); } if (arr[mid] >= arr[left]) { // 最小值在右边 left = mid; } else if (arr[mid] <= arr[right]) { // 最小值在左边 right = mid; } } return arr[right]; } /** * 测试代码 */ console.log(binSearchMin([3, 4, 5, 1, 2])); console.log(binSearchMin([2, 3, 4, 5, 1])); console.log(binSearchMin([2, 2, 2, 1, 1, 2])); console.log(binSearchMin([1]));

数字在排序数组中出现的次数

1. 题目

统计一个数字在排序数组中出现的次数。

2. 思路解析

题目说是排序数组,所以可以使用“二分查找”的思想。
一种思路是查找到指定数字,然后向前向后遍历,复杂度是 O(N)。
另一种是不需要遍历所有的数字,只需要找到数字在数组中的左右边界即可,做差即可得到出现次数。

3. 代码实现

/** * 寻找指定数字的左 / 右边界 * * @param {Array} nums * @param {*} target * @param {String} mode left | right 寻找左 | 右边界 */ function findBoundary(nums, target, mode) { let left = 0, right = nums.length - 1; while (left < right) { let mid = (right + left) >> 1; if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else if (mode === "left") { // nums[mid] === target // 如果下标是0或者前一个元素不等于target // 那么mid就是左边界 if (mid === 0 || nums[mid - 1] !== target) { return mid; } // 否则,继续在左部分遍历 right = mid - 1; } else if (mode === "right") { // nums[mid] === target // 如果下标是最后一位 或者 后一个元素不等于target // 那么mid就是右边界 if (mid === nums.length - 1 || nums[mid + 1] !== target) { return mid; } // 否则,继续在右部分遍历 left = mid + 1; } } // left === right if (nums[left] === target) { return left; } return -1; } /** * 寻找指定数字的出现次数 * * @param {Array} nums * @param {*} target */ function getTotalTimes(nums, target) { const length = nums.length; if (!length) { return 0; } return ( findBoundary(nums, target, "right") - findBoundary(nums, target, "left") + 1 ); } /** * 以下是测试代码 */ const nums = [1, 2, 3, 3, 3, 4, 5]; console.log(getTotalTimes(nums, 3));