题目难度: 中等
今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~
题目描述
搜索旋转数组。给定一个排序后的数组，包含 n 个整数，但这个数组已被旋转过很多次了，次数不详。请编写代码找出数组中的某个元素，假设数组元素原先是按升序排列的。若有多个相同元素，返回索引值最小的一个。
示例 1:
- 输入: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
- 输出: 8（元素 5 在该数组中的索引）
示例 2:
- 输入：arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
- 输出：-1 （没有找到）
提示:
- arr 长度范围在[1, 1000000]之间
题目思考
- 直接查找好找吗, 如何对问题进行简化?
解决方案
思路
- 根据题目描述, 这个数组虽然原始是排序的, 但现在经过了旋转, 而且其中还可能有重复元素
- 这时候如果仍然直接应用传统的二分查找的话, 就需要大量的条件判断, 比如先判断哪一侧有序, 再判断有序侧的区间起点终点和 target 的关系, 判断逻辑较为复杂
- 我们可以换一个角度分析, 如果能够找到旋转点, 这样就可以将当前数组划分成左右两个有序部分了, 然后就可以转换成经典的二分查找, 即依次对左右部分进行二分, 从而大大降低代码的复杂程度
- 那么如果找到旋转点呢? 很显然旋转点位于整个数组的无序侧, 所以我们也可以使用一个二分查找, 只需要找到无序侧, 然后继续对那一侧进行二分查找即可; 这里唯一需要注意的是, 如果无法判断是否无序, 需要额外判断当前终点是否是旋转点, 是的话需要直接跳出循环
- 找到旋转点后, 我们就可以对划分成的左右两部分依次应用传统二分查找了, 由于题目要求返回目标值的最小下标, 所以只有当左侧没找到的话才继续查找右侧, 如果都没找到的话就返回-1
- 下面的代码就对应了上面的整个过程, 并且有详细的注释, 方便大家理解
复杂度
- 时间复杂度
O(N): 最差情况(所有数字都相等)下, 需要遍历每个数字一遍 - 空间复杂度
O(1): 只使用了几个常数空间的变量
代码
class Solution:
def search(self, arr: List[int], target: int) -> int:
# 问题转换+找旋转点+两次二分
# 第一步, 先找旋转点, 将数组划分成左右两个有序部分
s, e = 0, len(arr) - 1
while s < e:
m = (s + e) >> 1
if arr[m] < arr[e]:
# 右侧有序, 旋转点必在[s,m]区间
e = m
elif arr[m] == arr[e]:
# 无法判断右侧是否有序, 将e减1后再次循环判断
if arr[e - 1] > arr[e]:
# 注意这里可能出现旋转点就是e的情况, 例如11121, 此时如果直接-1就错了, 需要额外判断, e是旋转点的话直接跳出循环
break
e -= 1
else:
# 右侧无序, 旋转点必在[m+1,e]区间
s = m + 1
# 此时旋转点即为e (注意不是s, 因为有可能是因为上面的break直接跳出的循环)
# 注意也有可能arr本身就是有序的, 此时得到的e就是下标0
# 也即原数组划分成了[0,e-1]和[e,len(arr)-1]两个有序区间
def bisearch(s, e):
# 常规有序数组二分找等于target的最小下标
res = float("inf")
while s <= e:
m = (s + e) >> 1
if arr[m] >= target:
if arr[m] == target:
res = min(res, m)
e = m - 1
else:
s = m + 1
return -1 if res == float("inf") else res
# 第二步, 再对左右两个有序部分应用常规二分找target, 如果左侧部分找到后就不再继续
l = bisearch(0, e - 1)
if l != -1:
return l
r = bisearch(e, len(arr) - 1)
if r != -1:
return r
return -1
大家可以在下面这些地方找到我~😊
我的公众号: 算法精选, 欢迎大家扫码关注~😊
京公网安备 11010502036488号