LeetCode Notes_#33 搜索旋转排序数组
LeetCodeContents
题目
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [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官方解答
//这个解法就是二分查找的应用，首先找到翻转的位置，就可以缩小一半的范围，然后再进行基本的二分查找，妙啊
class Solution {
int[] nums;
int target;
public int find_rotate_index(int left,int right){
//如果nums[0]<nums[n-1],说明没有被翻转,rotate_index为0
if(nums[left] < nums[right])
return 0;
//否则就寻找pivot的位置，注意这也是二分查找，反正就是查找一个数，刚好小于前一个数字，也就是第一次出现逆序的数
while(left <= right){
int pivot = (left + right)/2;
//如果直接找到满足条件的pivot,直接返回这个值
if(nums[pivot] > nums[pivot+1])
return pivot+1;
//否则
else{
//如果中间点小于最左侧点，说明在pivot位置之前就发生了逆序，调整右边界到pivot前一个位置
if(nums[pivot] < nums[left])
right = pivot - 1;
else
left = pivot + 1;
}
}
return 0;
}
//这里写了两个同名的search()函数，区别在于参数表不相同
public int search(int left,int right){
//不断地缩小查找的范围，直到左右边界相遇
while(left <= right){
//取中间点的方法就是直接求左右index的均值
int pivot = (left + right)/2;
if(nums[pivot] == target)
return pivot;
else{
//如果目标值小于中间点的值，那么将查找范围变成中间点的左边
if(target < nums[pivot])
right = pivot - 1;
//否则，将查找范围变成中间点的右边
else
left = pivot + 1;
}
}
//如果左右边界相遇后，还是没有返回值，说明找不到target,返回-1
return -1;
}
public int search(int[] nums, int target) {
this.nums = nums;
this.target = target;
int n = nums.length;
//首先考虑数组长度为0或者为1的情况
if(n == 0)
return -1;
if(n == 1)
return this.nums[0] == target?0:-1;
//left,right分别取为0,n-1，寻找最小的元素（翻转点）
int rotate_index = find_rotate_index(0,n-1);
//如果target就是最小的元素，直接返回这个位置的索引
if(nums[rotate_index] == target)
return rotate_index;
//如果没有被翻转（翻转位置为0）
if(rotate_index == 0)
return search(0,n-1);
//如果target比第一个数字小，说明一定在后半段,在后半段进行查找
if(target < nums[0])
return search(rotate_index,n-1);
return search(0,rotate_index);
}
}题解Review
- 题目所谓的旋转，其实是找到一个位置，将这个位置之前的几个数平移到数组的最后。对于题目中的例子来说这个位置就是4所在的位置。这样做的效果就是，有且只有一个数组下标为pivot的地方，满足
nums[pivot]>nums[pivot+1]。 - 所以第一步要找到这个pivot的位置。最朴素的想法就是从头到尾遍历，去找到满足条件的pivot,但是这样的复杂度就是O(n),不满足要求，O(log n)的复杂度应该是需要进行二分查找的。
- 首先考虑corner case:没有被翻转的情况，直接认为pivot = 0
- 二分查找算是一种模板型的代码吧，整体是while循环，循环体内部首先找到中间位置，然后判断目标位置和中间位置的关系，缩小一半的范围，继续循环。
- 找到pivot的位置后，比较target和nums[0]，就可以知道target位于左半部分还是右半部分,分别在左半部分和右半部分进行二分搜索，即可找到target的索引，且整体的时间复杂度是O(log n)。
- 先考虑corner case：rotate_index=0或者rotate_index=1
- 二分查找
自己的解答
class Solution {
int[] nums;
int target;
public int find_rotate_index(int left,int right){
//没有翻转的情况
if(nums[left] < nums[right])
return 0;
while(left <= right){
int pivot = (left + right)/2;
if(nums[pivot] > nums[pivot+1]){
//将最小的数字作为rotate_index
return pivot+1;
}else{
if(nums[pivot] >=nums[left]){
left = pivot + 1;
}else{
right = pivot - 1;
}
// if(nums[pivot] < nums[left])
// right = pivot - 1;
// else
// left = pivot + 1;
//注意这里两个条件是不可以互换位置的，因为在大于和小于之间还有一种等于的情况。
}
}
//循环结束还没有找到，也返回0
return 0;
}
public int search(int left,int right){
//到了调用这一步的时候，left和right之间的数组必然是顺序的，那么直接普通的二分查找就可以了
while(left <= right){
int pivot = (left + right)/2;
if(target == nums[pivot])
return pivot;
if(target > nums[pivot]){
left = pivot + 1;
}else
right = pivot - 1;
}
return -1;
}
public int search(int[] nums, int target) {
//为什么要定义两个类变量？因为定义完之后就可以直接被前面的两个函数访问到了
this.nums = nums;
this.target = target;
int len = nums.length;
if(len == 0)
return -1;
if(len == 1)
return target == nums[0]?0:-1;
int rotate_index = find_rotate_index(0, len-1);
if(nums[rotate_index] == target)
return rotate_index;
if(rotate_index == 0)
return search(0, len-1);
if(target >= nums[0])
return search(0, rotate_index);
return search(rotate_index, len-1);
}
}学习方法
我感觉自己去想这些套路确实效率很低，自己想很久想不出来，无法通过，一是费时间，二是打击信心，时间又并不是很充分，是一种难以持续的方式。不如先用简单点的流程，看解答抄代码->review思路->自己尝试写一遍。这样速度相对快些，可以一天看两三道类似的题目，反复学习揣摩一个基本算法和它的变形（比如这题就是二分搜索算法的变形），反而会效率比较高。