【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 可以大致分为两类，

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

复杂度分析

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

参考：

33 LeetCode题解.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)$ 由于旋转操作是 就地 完成的。

参考：

LeetCode官方题解