原文链接: https://leetcode-cn.com/problems/search-rotate-array-lcci

英文原文

Given a sorted array of n integers that has been rotated an unknown number of times, write code to find an element in the array. You may assume that the array was originally sorted in increasing order. If there are more than one target elements in the array, return the smallest index.

Example1:

 Input: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 5
 Output: 8 (the index of 5 in the array)

Example2:

 Input: arr = [15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14], target = 11
 Output: -1 (not found)

Note:

1. 1 <= arr.length <= 1000000

中文题目

搜索旋转数组。给定一个排序后的数组，包含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 （没有找到）

提示:

1. arr 长度范围在[1, 1000000]之间

通过代码

高赞题解

看快手的面经遇到了这道题，需要考虑的边界条件比较多，这里从易到难总结一下旋转数组相关的题，都是二分法的套路，看了这篇题解，一次搞定6道题！

189. 旋转数组

题目：

题解：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def reverse(left,right):
            while left<right:
                nums[left],nums[right]=nums[right],nums[left]
                left+=1
                right-=1
        n=len(nums)
        # 向右移动的位置k可能会大于n，因此对n取余
        k=k%n
        if k==0 or n<2:
            return 
        # 以此为例：nums = [1,2,3,4,5,6,7], k = 3
        # 先整个数组反转：[7,6,5,4,3,2,1]
        reverse(0,n-1)
        # 前k个反转：[5,6,7,4,3,2,1]
        reverse(0,k-1)
        # 后n-k个反转：[5,6,7,1,2,3,4]
        reverse(k,n-1)

153. 寻找旋转排序数组中的最小值

题目：

• nums 中的所有整数都是 唯一 的
• nums 原来是一个升序排序的数组，但在预先未知的某个点上进行了旋转

题解：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n=len(nums)
        left=0
        right=n-1
        # 这里控制条件没取等号，取等号大多是为了在while中直return mid，不取等号就跳出while返回l的值。
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[right]:
                # 中间数字大于右边数字，比如[3,4,5,1,2]，则左侧是有序上升的，最小值在右侧
                left=mid+1
            else:
                # 中间数字小于等于右边数字，比如[6,7,1,2,3,4,5]，则右侧是有序上升的，最小值在左侧
                right=mid
        return nums[left]

154. 寻找旋转排序数组中的最小值 II

题目：

• 这道题是 153.寻找旋转排序数组中的最小值 的延伸题目。
• 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？

题解：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        n=len(nums)
        left=0
        right=n-1
        # 这里控制条件没取等号，取等号大多是为了在while中直return mid，不取等号就跳出while返回l的值。
        while left<right:
            mid=left+(right-left)//2
            if nums[mid]>nums[right]:
                # 中间数字大于右边数字，比如[3,4,5,1,2]，则左侧是有序上升的，最小值在右侧
                left=mid+1
            elif nums[mid]<nums[right]:
                # 中间数字小于等于右边数字，比如[6,7,1,2,3,4,5]，则右侧是有序上升的，最小值在左侧
                right=mid
            else:
                # 中间数字等于右边数字，比如[2,3,1,1,1]或者[4,1,2,3,3,3,3]
                # 则重复数字可能为最小值，也可能最小值在重复值的左侧
                # 所以将right左移一位
                right-=1
        return nums[left]        

平均时间复杂度为 O(logn)，而在最坏情况下，如果数组中的元素完全相同，那么 while 循环就需要执行 n次，每次忽略区间的右端点，时间复杂度为 O(n)。

上面两道题是在旋转数组里寻找最小值，下面两道题是在旋转数组里寻找指定的值，这两道题的区别也是存不存在重复值。

33. 搜索旋转排序数组

题目：

题解：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l,r=0,len(nums)-1
        # 这里控制条件取等号，取等号大多是为了在while中直return mid，不取等号就跳出while返回l的值。
        while l<=r:
            mid=l+(r-l)//2
            # 中间值即为target，直接返回
            if nums[mid]==target:
                return mid
            # 左半部分是有序
            if nums[0]<=nums[mid]:
                # target落在左半部分有序区域内
                if nums[0]<=target<nums[mid]:
                    r=mid-1
                else:
                    # target落在右半部分无序区域内
                    l=mid+1
            else: # 右半部分是有序
                # target落在右半部分有序区域内
                if nums[mid]<target<=nums[len(nums)-1]:
                    l=mid+1
                else:
                    # target落在左半部分无序区域内
                    r=mid-1
        return -1

81. 搜索旋转排序数组 II

题目：

题解：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return False
        l,r=0,len(nums)-1
        while l<=r:
            # 重点在于处理重复数字
            # 左边有重复数字，将左边界右移
            while l<r and nums[l]==nums[l+1]:
                l+=1
            # 右边有重复数字，将右边界左移
            while l<r and nums[r]==nums[r-1]:
                r-=1
            mid=(l+r)//2
            if nums[mid]==target:
                return True
            # 左半部分有序
            if nums[0]<=nums[mid]:
                if nums[0]<=target<nums[mid]:
                    r=mid-1
                else:
                    l=mid+1
            else:# 右半部分有序
                if nums[mid]<target<=nums[len(nums)-1]:
                    l=mid+1
                else:
                    r=mid-1
        return False

面试题 10.03. 搜索旋转数组

这道题与81题很像，唯一的区别就是81题要求只要存在target就返回true，而这道题要 返回多个重复target中最靠前的那个
题目：

题解： 此题边界case很多，与上面的几道题相比，注释里给出了三个重点改变，仔细体会。

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        n=len(arr)
        left=0
        right=n-1
        while left<=right:
            # 重点1：当left符合时直接返回, 因为找的是最小的索引
            if arr[left]==target:
                return left
            mid=left+(right-left)//2
            # 重点2：当中间值等于目标值，将右边界移到中间，因为左边可能还有相等的值
            if arr[mid]==target:
                right=mid
            elif arr[0]<arr[mid]:
                if arr[0]<=target<arr[mid]:
                    right=mid-1
                else:
                    left=mid+1
            elif arr[0]>arr[mid]:
                if arr[mid]<target<=arr[n-1]:
                    left=mid+1
                else:
                    right=mid-1
            else:
                # 重点3：当中间数字与左边数字相等时，将左边界右移
                    left+=1
        return -1

---

以上就是关于旋转数组的6道题，刷题要常总结归类，才能举一反三！我是乐清，如果你觉得这篇总结对你有帮助，求赞 求收藏 求关注，如果有不懂的地方或者想看什么题型的总结可评论留言。

统计信息

通过次数	提交次数	AC比率
14136	35841	39.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言