搜索旋转排序数组
LeetCode 第 33 题：搜索旋转排序数组
传送门：搜索旋转排序数组。难度：中等。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回
-1。你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4示例 2:
输入: nums = [4,5,6,7,0,1,2], target = 3 输出: -1
思路：二分查找，特别要注意边界条件的判断。
1、注意一个细节：
int mid = left + (right - left) / 2;
在只有两个数的区间 找中点的时候，就只会得到
，所以要将 nums[mid] 和 nums[right] 进行判断。并且
while 里面是 left <= right 必须要能够取等号。这时可以使用
int mid = left + (right - left + 1) / 2;
让中点靠近右边。
2、这道题应用了旋转数组的一个性质，那就是：==分割以后，有且只有其中的一部分是顺序数组，另一个数组是仍是旋转数组==；
3、一个重要的条件：你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是 级别。
总结：1、旋转数组任意分割以后，一定有一边是顺序数组，另一边是还是旋转数组
2、特别要注意分类讨论的情况；
3、这道题比较使用使用循环来做，递归的话容易写错。
4、特别注意临界情况，体会 mid = left + (right - left) / 2; 与 int mid = left + (right - left + 1) / 2; 这两者的区别。
Python 代码：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
if nums[mid] < nums[r]:
# nums[mid + 1:r] 包括左右区间端点有序
if nums[mid] < target <= nums[r]:
l = mid + 1
else:
r = mid - 1
else:
# nums[l:mid - 1] 包括左右区间端点有序
if nums[l] <= target < nums[mid]:
r = mid - 1
else:
l = mid + 1
return -1
Java 代码：
class Solution {
public int search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return -1;
}
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < nums[right]) {
// 从 mid 到 right 都是顺序数组
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
// 其余的情况就在右边了
right = mid - 1;
}
} else {
// 此时 left 到 mid 是顺序数组
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return -1;
}
}
使用“逼近”方式的二分法。
Python 代码：注意：左右区间“收缩”的方式要一致
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] < nums[r]:
# [7,8,9,1,2,3,4,5,6] ，后半部分有序
if nums[mid] <= target <= nums[r]:
l = mid
else:
r = mid - 1
else:
# [4,5,6,7,8,9,0,1,2]，前半部分有序
if nums[l] <= target <= nums[mid - 1]:
r = mid - 1
else:
l = mid
return l if nums[l] == target else -1
LeetCode 第 81 题：搜索旋转排序数组 II
传送门：81. 搜索旋转排序数组 II。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,0,1,2,2,5,6]可能变为[2,5,6,0,0,1,2])。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回
true，否则返回false。示例 1:
输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true示例 2:
输入: nums = [2,5,6,0,0,1,2], target = 3 输出: false进阶:
- 这是 搜索旋转排序数组 的延伸题目，本题中的
nums可能包含重复元素。- 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
思路：这道题在第 33 题的基础上，加上了可能有重复元素的条件。重点在于：nums[mid] == nums[right] 的判断，因为“可能有重复元素”此时不能断定哪一边一定是旋转数组，哪一边一定是顺序数组，因此，只能够去掉 right。
Java 代码：
class Solution {
public boolean search(int[] nums, int target) {
int len = nums.length;
if (len == 0) {
return false;
}
int left = 0;
int right = len - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[mid] == nums[right]) {
right--;
} else if (nums[mid] < nums[right]) {
// mid 到 right 是顺序数组
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
// nums[mid] > nums[right]
// left 到 mid 是顺序数组
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
}
return false;
}
}
Python 代码：
class Solution:
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: bool
"""
size = len(nums)
if size == 0:
return False
l = 0
r = size - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] < nums[r]:
# 后面是有序的
# [2,3,4,5,5,6,6,7]
if nums[mid] <= target <= nums[r]:
l = mid
else:
r = mid - 1
elif nums[mid] > nums[r]:
# [3,4,5,5,6,6,7,2]
if nums[l] <= target <= nums[mid - 1]:
r = mid - 1
else:
l = mid
else:
assert nums[mid] == nums[r]
if nums[r] == target:
return True
# 右边不是才删除
r = r - 1
return nums[l] == target
寻找旋转排序数组中的最小值
LeetCode 第 153 题：寻找旋转排序数组中的最小值
传送门：153. 寻找旋转排序数组中的最小值。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。请找出其中最小的元素。
你可以假设数组中不存在重复元素。
示例 1:
输入: [3,4,5,1,2] 输出: 1示例 2:
输入: [4,5,6,7,0,1,2] 输出: 0
分析：这个问题中给出的数组没有重复元素。还是利用旋转数组的那个性质，另外不要把问题想得过于复杂。
下面这个模板是要记住的。
如何理解这个二分法：
1、nums[mid] < nums[right]：例子：[8,9,1,2,3,4,5,6]，此时 mid 有可能是最小。
2、否则，nums[mid] > nums[right]：例子：[7,8,9,10,1,2]，mid 肯定不是最小。
3、还可以使用分治的思想解决这个问题。
Python 代码：二分法
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
raise Exception('程序出错')
if size == 1:
return nums[0]
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
# [7,8,1,2,3,4,5,6]
if nums[mid] < nums[r]:
# mid 有可能是最小元素，所以，不能排除它
r = mid
else:
# [3,4,5,6,7,8,1,2]
# 此时 mid 肯定不是最小元素
assert nums[mid] > nums[r]
l = mid + 1
# 一定存在最小元素，因此无须再做判断
return nums[l]
Python 代码2：分治法
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
raise Exception('程序出错')
if size == 1:
return nums[0]
return self.__findMin(nums, 0, size - 1)
def __findMin(self, nums, left, right):
if left == right:
return nums[left]
if left + 1 == right:
return min(nums[left], nums[right])
mid = left + (right - left) // 2
return min(self.__findMin(nums, left, mid), self.__findMin(nums, mid + 1, right))
LeetCode 第 154 题：找旋转排序数组中的最小值 II
传送门： 154. 寻找旋转排序数组中的最小值 II。
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组
[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。请找出其中最小的元素。
注意数组中可能存在重复的元素。
示例 1：
输入: [1,3,5] 输出: 1示例 2：
输入: [2,2,2,0,1] 输出: 0说明：
- 这道题是 寻找旋转排序数组中的最小值 的延伸题目。
- 允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
分析：注意数组中可能存在重复的元素。
注意点1：left < right这是模板二分法的写法。
注意点2：nums[mid] < nums[right] 进行比较。
Python 代码：
class Solution:
def findMin(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
size = len(nums)
if size == 0:
return Exception('程序出错')
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < nums[r]:
# mid 有可能是最小值
# [7,8,1,2,3]
r = mid
elif nums[mid] > nums[r]:
# mid 肯定不是最小值
# [7,8,9,10,11,1,2,3]
l = mid + 1
else:
# 都有可能，所以就把 r 排除了
# [1,1,1,1,1,0,1]
assert nums[mid] == nums[r]
r = r - 1
return nums[l]
Java 代码：
class Solution {
public int findMin(int[] nums) {
int len = nums.length;
if (len == 0) {
return 0;
}
int first = 0;
int last = len - 1;
while (first < last) {
int mid = first + (last - first) / 2;
if (nums[mid] > nums[last]) {
// 例如：[7,8,9,10,11,12,1,2]，最小的一定不在前面，也一定不是 mid
// 所以可以放心地 + 1
first = mid + 1;
} else if (nums[mid] == nums[last]) {
// [1,1,1,1,0,1] 和 [1,0,1,1,1,1] 这两种情况，只能把 last 给排除掉
// 因为 nums[mid] == nums[last] 相等，最小元素不会丢掉
last = last - 1;
} else {
// 当 nums[mid] < nums[last] 的时候
// mid 有可能是最小解，不能写成 last = mid - 1
last = mid;
}
}
// 这里 return nums[last] 也是可以的，因为跳出那层 while 的时候有，first = last
return nums[first];
}
}
此时，还可以使用分治的思想。
如果使用分治法，代码和第 153 题是一模一样的。
同《剑指 Offer》第 11 题：旋转数组中的最小数字。
传送门：AcWing 22. 旋转数组的最小数字 。
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个升序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
数组可能包含重复项。
注意：数组内所含元素非负，若数组大小为0，请返回-1。
样例
输入：nums=[2,2,2,0,1] 输出：0
分析：使用二分查找算法解决，要注意一些细节，从后向前。
LeetCode 第 189 题：生成旋转数组
传送门：英文网址：189. Rotate Array ，中文网址：189. 旋转数组 。
给定一个数组，将数组中的元素向右移动 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) 的原地算法。
Python 代码：
class Solution:
def rotate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: void Do not return anything, modify nums in-place instead.
"""
# 先处理极端情况
if len(nums) == 0 or k <= 0:
return
k = k % len(nums)
# 做下面 3 个逆转动作的时候，注意边界条件
# 技巧就是举具体的例子
self.__reverse(nums, 0, len(nums) - 1)
self.__reverse(nums, 0, k - 1)
self.__reverse(nums, k, len(nums) - 1)
def __reverse(self, nums, index1, index2):
"""
将数组 [index1,index2] 区间内的元素进行逆转
:param nums:
:param index1:
:param index2:
:return:
"""
while index1 < index2:
nums[index1], nums[index2] = nums[index2], nums[index1]
index1 += 1
index2 -= 1
if __name__ == '__main__':
nums = [1, 2, 3, 4, 5, 6, 7]
k = 3
s = Solution()
s.rotate(nums, k)
print(nums)
（本节完）
