第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0033. 搜索旋转排序数组

题目地址(33. 搜索旋转排序数组)

题目描述

1
给你一个升序排列的整数数组 nums ,和一个整数 target 。
2
3
假设按照升序排序的数组在预先未知的某个点上进行了旋转。(例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
4
5
请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
6
7
8
示例 1:
9
10
输入:nums = [4,5,6,7,0,1,2], target = 0
11
输出:4
12
示例 2:
13
14
输入:nums = [4,5,6,7,0,1,2], target = 3
15
输出:-1
16
示例 3:
17
18
输入:nums = [1], target = 0
19
输出:-1
20
21
22
提示:
23
24
1 <= nums.length <= 5000
25
-10^4 <= nums[i] <= 10^4
26
nums 中的每个值都 独一无二
27
nums 肯定会在某个点上旋转
28
-10^4 <= target <= 10^4
Copied!

前置知识

  • 数组
  • 二分法

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

这是一个我在网上看到的前端头条技术终面的一个算法题。
题目要求时间复杂度为 logn,因此基本就是二分法了。 这道题目不是直接的有序数组,不然就是 easy 了。
首先要知道,我们随便选择一个点,将数组分为前后两部分,其中一部分一定是有序的。
具体步骤:
  • 我们可以先找出 mid,然后根据 mid 来判断,mid 是在有序的部分还是无序的部分
假如 mid 小于 start,则 mid 一定在右边有序部分。 假如 mid 大于等于 start, 则 mid 一定在左边有序部分。
注意等号的考虑
  • 然后我们继续判断 target 在哪一部分, 我们就可以舍弃另一部分了
我们只需要比较 target 和有序部分的边界关系就行了。 比如 mid 在右侧有序部分,即[mid, end] 那么我们只需要判断 target >= mid && target <= end 就能知道 target 在右侧有序部分,我们就 可以舍弃左边部分了(start = mid + 1), 反之亦然。
我们以([6,7,8,1,2,3,4,5], 4)为例讲解一下:
search-in-rotated-sorted-array-1
search-in-rotated-sorted-array-1

关键点解析

  • 二分法
  • 找出有序区间,然后根据 target 是否在有序区间舍弃一半元素

代码

  • 语言支持: Javascript,Python3
1
/*
2
* @lc app=leetcode id=33 lang=javascript
3
*
4
* [33] Search in Rotated Sorted Array
5
*/
6
/**
7
* @param {number[]} nums
8
* @param {number} target
9
* @return {number}
10
*/
11
var search = function (nums, target) {
12
// 时间复杂度:O(logn)
13
// 空间复杂度:O(1)
14
// [6,7,8,1,2,3,4,5]
15
let start = 0;
16
let end = nums.length - 1;
17
18
while (start <= end) {
19
const mid = start + ((end - start) >> 1);
20
if (nums[mid] === target) return mid;
21
22
// [start, mid]有序
23
24
// ️⚠️注意这里的等号
25
if (nums[mid] >= nums[start]) {
26
//target 在 [start, mid] 之间
27
28
// 其实target不可能等于nums[mid], 但是为了对称,我还是加上了等号
29
if (target >= nums[start] && target <= nums[mid]) {
30
end = mid - 1;
31
} else {
32
//target 不在 [start, mid] 之间
33
start = mid + 1;
34
}
35
} else {
36
// [mid, end]有序
37
38
// target 在 [mid, end] 之间
39
if (target >= nums[mid] && target <= nums[end]) {
40
start = mid + 1;
41
} else {
42
// target 不在 [mid, end] 之间
43
end = mid - 1;
44
}
45
}
46
}
47
48
return -1;
49
};
Copied!
Python3 Code:
1
class Solution:
2
def search(self, nums: List[int], target: int) -> int:
3
"""用二分法,先判断左右两边哪一边是有序的,再判断是否在有序的列表之内"""
4
if len(nums) <= 0:
5
return -1
6
7
left = 0
8
right = len(nums) - 1
9
while left < right:
10
mid = (right - left) // 2 + left
11
if nums[mid] == target:
12
return mid
13
14
# 如果中间的值大于最左边的值,说明左边有序
15
if nums[mid] > nums[left]:
16
if nums[left] <= target <= nums[mid]:
17
right = mid
18
else:
19
# 这里 +1,因为上面是 <= 符号
20
left = mid + 1
21
# 否则右边有序
22
else:
23
# 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列
24
if nums[mid+1] <= target <= nums[right]:
25
left = mid + 1
26
else:
27
right = mid
28
29
return left if nums[left] == target else -1
Copied!
复杂度分析
  • 时间复杂度:$O(logN)$
  • 空间复杂度:$O(1)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。