二分法之旋转数组

旋转数组

旋转数组是指将一个按照升序排序好的数组进行旋转操作，具体来讲就是讲排序好的数组的前k个元素放到数组的尾部上去。例如，将数组[1,2,3,4,5,6]的前3个元素进行旋转变为[4,5,6,1,2,3]，然后就是查找指定的元素，或者返回数组中最小的元素等等算法要求，也会根据难易程度，规定数组中是否存在重复元素。
这类题目一般都是二分法求解的，接下来我们就通过实战来学习这类问题的解吧

参考：
【旋转数组】从易到难，各个击破！

189. 轮转数组

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
输入：nums = [-1,-100,3,99], k = 2 输出：[3,99,-1,-100]

分析：
最直接的方法直接将前len(nums)-k个元素接到数组后面就可以了，但这样需要创建新的空间，不符合题意

这道题属于左旋数组和字符串这一类的题目，对于左旋字符串建议去看代码随想录，讲解得不错。对于左旋的题我们的思路为：
1）先翻转前k个元素
2）再翻转后面len(nums)-k个元素
3）最后翻转整个数组
注意：这里题目的要求与左旋不是完全一致的，这里其实是右旋，所以需要修改为：
1）先翻转前len(nums)-k个元素
2）再翻转后面k个元素
3）最后翻转整个数组
此外还需要注意一点的事，k的大小可能是大于整个数组的长度的，所以需要对k进行取余的运算
或者，即标准右旋的操作：
1）先翻转整个数组
2）再翻转前k个元素
3）最后翻转后面len(nums)-k个元素
可以发现，左旋跟右旋的区别在于，左旋最后旋转整个数组，而右旋最先旋转整个数组

Python源码：

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        def reverse(nums, left, right):
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        if k >= len(nums): k = k % len(nums)
        reverse(nums, 0, len(nums)-k-1)
        reverse(nums, len(nums)-k, len(nums)-1)
        reverse(nums, 0, len(nums)-1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

相似题目：
剑指 Offer 58 - II. 左旋转字符串
796. 旋转字符串
61. 旋转链表

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

已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
输入：nums = [3,4,5,1,2] 输出：1
输入：nums = [4,5,6,7,0,1,2] 输出：0

优秀题解：
二分查找：为什么左右不对称？只比较mid与right的原因（C++, Java, Python3）

分析：
1）中间值与当前范围中的right值相比较
2）如果中间值大于right值就说明，最小值在中间值的右边，即left=mid+1
3）如果中间值小于right值就说明，最小值在中间值的左边，或者就中间值，即right=mid
4）最后返回left值

Python源码：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            else:
                right = mid
        return nums[left]
1
2
3
4
5
6
7
8
9
10

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

与《153. 寻找旋转排序数组中的最小值》唯一不同的就是，这里的数组中有可能存在重复的元素
输入：nums = [1,3,5] 输出：1
输入：nums = [2,2,2,0,1] 输出：0

优秀题解：
寻找旋转排序数组中的最小值 II（二分法，极简，图解）

分析：
与《153. 寻找旋转排序数组中的最小值》不同的是有可能存在重复的元素
那针对重复的数字，即可能存在nums[mid] == nums[right]的可能性
碰到这种情况，我们只要缩小right的范围就可以了，即right -= 1

Python源码：

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        while left < right:
            mid = (left + right) // 2
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]
1
2
3
4
5
6
7
8
9
10
11
12

33. 搜索旋转排序数组

整数数组 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,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
输入：nums = [4,5,6,7,0,1,2], target = 0 输出：4
输入：nums = [4,5,6,7,0,1,2], target = 3 输出：-1

优秀题解：
搜索旋转排序数组
多思路完全攻略，🤷‍♀️必须秒懂！

分析：
核心思想：
将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能有序，可能无序。就这样循环
1）将中间值与当前左边的值进行比较，如果中间值大于等于当前左边的值，说明中间值的左边是有序的。然后再判断目标值是否在左边这个有序数组中，如果在，缩小右边范围；如果不在，则缩小左边范围
2）如果中间值小于当前左边的值，说明中间值的右边是有序的。然后再判断目标值是否在右边这个有序数组中，如果在，缩小左边范围；如果不在，则缩小右边范围

Python源码：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return mid

            if nums[mid] >= nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

81. 搜索旋转排序数组 II

与《33. 搜索旋转排序数组》唯一不同的就是，这里的数组中有可能存在重复的元素
输入：nums = [2,5,6,0,0,1,2], target = 0 输出：true
输入：nums = [2,5,6,0,0,1,2], target = 3 输出：false

优秀题解：
搜索旋转排序数组 II

分析：
与《33. 搜索旋转排序数组》唯一不同的就是，这里的数组中有可能存在重复的元素
针对这一点，我们对应的变化在于
之前是：将中间值与当前左边的值进行比较，如果中间值大于等于当前左边的值，说明中间值的左边是有序的
现在因为数组的元素有可能是重复的，当中间值与当前左边的值相等时，不能说明中间值的左边是有序的，例如[1,0,1,1,1]
如果当中间值等于当前左边的值时，我们应该缩小左边的范围再进行判断，即left += 1

Python源码：

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums)-1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return True

            if nums[mid] == nums[left]:
                left += 1
            elif nums[mid] > nums[left]:
                if nums[left] <= target <= nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] <= target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1

        return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题 10.03. 搜索旋转数组

与《81. 搜索旋转排序数组 II》唯一不同的就是，这里不再是判断元素是否存在于数组中了，而是返回查找元素的下标，若有多个相同元素，返回索引值最小的一个。

优秀题解：
【旋转数组】从易到难，各个击破！

分析：
与《81. 搜索旋转排序数组 II》相比主要注意两点：
1）当left等于target时直接返回, 因为找的是最小的索引
2）当中间值等于目标值时，将右边界移到中间，因为左边可能还有相等的值
如果中间值不等于目标值，则需要按照《81. 搜索旋转排序数组 II》的方式继续缩小范围

Python源码：

class Solution:
    def search(self, arr: List[int], target: int) -> int:
        left, right = 0, len(arr)-1
        while left <= right:
            # 重点1：当left符合时直接返回, 因为找的是最小的索引
            if arr[left] == target: return left
            mid = (left + right) // 2
            # 重点2：当中间值等于目标值，将右边界移到中间，因为左边可能还有相等的值
            if arr[mid] == target:
                right = mid
            # 重点3：当中间数字与左边数字相等时，将左边界右移
            elif arr[mid] == arr[left]:
                left += 1
            elif arr[mid] > arr[left]:
                if arr[left] <= target <= arr[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if arr[mid] <= target <= arr[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        
        return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25