Skip to content

Latest commit

 

History

History
151 lines (111 loc) · 5.99 KB

0081.md

File metadata and controls

151 lines (111 loc) · 5.99 KB
title description keywords
81. 搜索旋转排序数组 II
LeetCode 81. 搜索旋转排序数组 II题解，Search in Rotated Sorted Array II，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。
LeetCode
81. 搜索旋转排序数组 II
搜索旋转排序数组 II
Search in Rotated Sorted Array II
解题思路
数组
二分查找

81. 搜索旋转排序数组 II

🟠 Medium  🔖  数组 二分查找  🔗 力扣 LeetCode

题目

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] ( 0-indexed ). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].

Given the array nums after the rotation and an integer target, return true iftarget is innums , orfalse if it is not innums .

You must decrease the overall operation steps as much as possible.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0

Output: true

Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3

Output: false

Constraints:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • nums is guaranteed to be rotated at some pivot.
  • -10^4 <= target <= 10^4

Follow up: This problem is similar to Search in Rotated SortedArray, but nums may contain duplicates. Would this affect the runtime complexity? How and why?

题目大意

已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。

给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums 中存在这个目标值 target ，则返回 true ，否则返回 false 。

你必须尽可能减少整个操作步骤。

进阶：

此题与 搜索旋转排序数组 相似，但本题中的 nums 可能包含 重复 元素。这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？

解题思路

这道题与第 33 题 搜索旋转排序数组 相似，区别是本题中的 nums 可能包含 重复 元素，因此需要增加第 3 步，跳过潜在的重复性。

由于数组是部分有序的，可以利用 二分查找 的思想来解决这个问题。与普通的二分查找不同，这里数组被旋转过，所以需要通过额外的判断来确定二分查找的方向。

  1. 首先，数组依然可以通过中间值 mid 将左右部分分为有序和无序两部分。

  2. 每次找到中间位置 mid，先检查 nums[mid] 是否等于目标值。如果相等，直接返回索引。

  3. 接着检查 nums[left] 和 nums[mid] 值是否相同，如果相同，则需要处理重复项，在这种情况下，可以增加 left 以跳过潜在的重复项。

  4. 通过 nums[left] 和 nums[mid] 的大小关系来判断哪一部分是有序的。

    • 通过比较 nums[left] 和 nums[mid] 可以判断左半部分是否有序。
    • 如果 nums[left] <= nums[mid]，说明左半部分是有序的，否则右半部分有序。

  5. 判断目标值的位置：

    • 如果左半部分有序，且目标值落在 nums[left] 到 nums[mid] 之间，那么缩小搜索范围至左半部分，否则去右半部分继续查找。
    • 如果右半部分有序，且目标值落在 nums[mid] 到 nums[right] 之间，那么缩小搜索范围至右半部分，否则去左半部分继续查找。

  6. 不断缩小查找区间，直到找到目标值，或者使得 left > right时返回 -1。

复杂度分析

  • 时间复杂度：O(log n)，这是二分查找的时间复杂度，每次查找时将搜索范围缩小一半。
  • 空间复杂度：O(1)，只用了常量级的额外空间。

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
	let left = 0;
	let right = nums.length - 1;

	while (left <= right) {
		let mid = Math.floor((left + right) / 2);

		// 找到目标值
		if (nums[mid] === target) {
			return mid;
		}

		// 跳过潜在的重复项
		if (nums[left] == nums[mid]) {
			left++;
			continue;
		}

		// 判断左半部分是否有序
		if (nums[left] <= nums[mid]) {
			// 如果 target 在左半部分的范围内
			if (nums[left] <= target && target < nums[mid]) {
				right = mid - 1; // 缩小到左半部分
			} else {
				left = mid + 1; // 否则缩小到右半部分
			}
		}
		// 否则右半部分有序
		else {
			// 如果 target 在右半部分的范围内
			if (nums[mid] < target && target <= nums[right]) {
				left = mid + 1; // 缩小到右半部分
			} else {
				right = mid - 1; // 否则缩小到左半部分
			}
		}
	}

	// 没有找到目标值
	return -1;
};

相关题目

题号 标题 题解 标签 难度 力扣
33 搜索旋转排序数组 [✓] 数组 二分查找 🟠 🀄️ 🔗