【LeetCode】33. 搜索旋转排序数组（查找目标值） & 189. 旋转数组 （将数组中的元素向右移动 k 个位置）& 48. 旋转图像

一、搜索旋转排序数组（查找目标值）

1. 题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 $O(logn)$ 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

2. 解题思路

题目要求 $O(logn)$ 的时间复杂度，基本可以断定本题是需要使用二分查找，怎么分是关键。

由于题目说数字了无重复，举个例子：
1 2 3 4 5 6 7 可以大致分为两类，

1. 第一类 2 3 4 5 6 7 1 这种，也就是 $nums[left]<=nums[mid]$。此例子中就是 $2<=5$。这种情况下，前半部分有序。因此如果 $nums[left]<=target<nums[mid]$，则在前半部分找，否则去后半部分找。
2. 第二类 6 7 1 2 3 4 5 这种，也就是 $nums[left]>nums[mid]$。此例子中就是 $6>2$。这种情况下，后半部分有序。因此如果 $nums[mid]<target<=nums[right]$，则在后半部分找，否则去前半部分找。

3. 代码

先复习一下二分法：

Java

public int search(int[] nums, int target) {
   
    int lo = 0, hi = nums.length - 1, mid = 0;
    while (lo <= hi) {
   
        mid = lo + ((hi - lo) >> 1);  // >> 符号即除以2
        if (nums[mid] == target) {
   
            return mid;
        }
        if (nums[mid] < target) {
   
            lo = mid + 1;
        } else {
   
            hi = mid - 1;
        }
    }
    return -1;
}

注：

如果用 $mid=(left+right)/2$，在运行二分查找程序时可能溢出超时。
因为如果 $left$ 和 $right$ 相加超过 $int$ 表示的最大范围时就会溢出变为负数。
所以如果想避免溢出，不能使用 $mid=(left+right)/2$，应该使用 $mid=left+(right-left)/2$.

Python题解：

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        if not nums:
            return -1
        l = 0
        r = len(nums) - 1
        while (l <= r):
            # mid = (l + r) // 2
            mid = l + (r- l) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] >= nums[l]: # 前半部分有序
                # 再判断 target 是在 mid 左边还是右边，即传统二分法
                if target >= nums[l] and target < nums[mid]:  # 在左边有序部分找
                    r = mid - 1
                else:
                    l = mid + 1
            else:                    # 后半部分有序
                if target > nums[mid] and target <= nums[r]:   # 注意 = 号放在没有 mid 的一侧，否则不对
                    l = mid + 1
                else:
                    r = mid - 1
        return -1   # 跳出循环说明全部搜索完都找不见

=================================================================

旋转数组 （将数组中的元素向右移动 k 个位置）

1. 题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。

2. 解题思路 & 代码

环状替代

可以理解为理解。把元素看做同学，把下标看做座位，大家换座位。第一个同学离开座位去第k+1个座位，第k+1个座位的同学被挤出去了，他就去坐他后k个座位，如此反复。但是会出现一种情况，就是其中一个同学被挤开之后，坐到了第一个同学的位置（空位置，没人被挤出来），但是此时还有人没有调换位置，这样就顺着让第二个同学换位置。 那么什么时候就可以保证每个同学都换完了呢？n个同学，换n次，所以用一个count来计数即可。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """ Do not return anything, modify nums in-place instead. """
        L  = len(nums)
        k = k % L
        count = 0         # 记录交换位置的次数，n个同学一共需要换n次
       # nums.leng为偶数时，会形成多个换环 1 2 3 4（1 3 1,2 4 2,3,1,3） ，为奇数时则只有一个环 1 2 3 4 5 （1 3 5 2 4 1），i=0不会增加
        start = 0
        while count < L:
            cur = start       # 当前坐标， 从0位置开始换位子
            pre = nums[cur]   # 前一个坐标

            while True:       # 循环暂停，回到起始位置，角落无人
                next = (cur + k) % L # 下一个坐标
                temp = nums[next]      # 来到角落...
                # 交换
                nums[next] = pre
                pre = temp
                cur = next
                count += 1
                
                if start == cur:
                    break
            start += 1

复杂度分析

1. 时间复杂度：O(n) 。只遍历了每个元素一次。
2. 空间复杂度：O(1) 。使用了常数个额外空间。

参考：

1. 33 LeetCode题解.
2. 189 LeetCode题解

=================================================================

48. 旋转图像

一、题目描述

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

二、解题思路 & 代码

转置加翻转

最直接的想法是先转置矩阵，然后翻转每一行

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

        # transpose matrix
        for i in range(n):
            for j in range(i, n):  # 注意起始点
                temp = matrix[i][j]
                matrix[i][j] = matrix[j][i]
                matrix[j][i] = temp
        
        # reverse each row
        for i in range(n):
            for j in range(n//2):  # 注意终点
                temp = matrix[i][j]
                matrix[i][j] = matrix[i][n-j-1]
                matrix[i][n-j-1] = temp

• 时间复杂度：$O(N^2)$.
• 空间复杂度：$O(1)$ 由于旋转操作是 就地 完成的。

参考：

1. LeetCode官方题解