摘要:如果左边的点比右边的大,说明这两个点之间有一个旋转点,导致了不再有序。因为只有一个旋转点,所以一分为二后,肯定有一半是有序的。
Search in Rotated Sorted Array I
Suppose a sorted array is rotated at some pivot unknown to you beforehand.(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
最新更新请见:https://yanjia.me/zh/2019/01/...
二分法 复杂度时间 O(logN) 空间 O(1)
思路平时我们二分法的时候,直接判断下中点和目标的关系,就可以知道目标在左半部分还是右半部份了,这背后其实隐含一个假设,那就是从起点到终点是一段有序的序列。而本题中,如果我们还想继续做二分法,这个假设就不存在了,因为从起点到终点有可能有个断片!不过,旋转有序数组有一个特点,假设本身是个升序序列,从左向右。如果左边的点比右边的点小,说明这两个点之间是有序的,不存在旋转点。如果左边的点比右边的大,说明这两个点之间有一个旋转点,导致了不再有序。因为只有一个旋转点,所以一分为二后,肯定有一半是有序的。所以,我们还是可以用二分法,不过要先判断左半边有序还是右半边有序。如果左半边有序,则直接将目标和左半边的边界比较,就知道目标在不在左半边了,如果不在左半边肯定在右半边。同理,如果右半边有序,则直接将目标和右半边的边界比较,就知道目标在不在右半边了,如果不在右半边肯定在左半边。这样就完成了二分。
注意这里要注意二分时候的边界条件,一般来说我们要找某个确定的目标时,边界条件为:
min = 0, max = length - 1; if(min <= max){ min = mid + 1 max = mid - 1 }
另外,判断左半边是否有序的条件是:nums[min] <= nums[mid],而判断是否在某一个有序区间,则要包含那个区间较远的那一头
代码迭代写法
public class Solution { public int search(int[] nums, int target) { int min = 0, max = nums.length - 1, mid = 0; while(min <= max){ mid = (min + max) / 2; if(nums[mid] == target){ return mid; } // 如果左半部分是有序的 if(nums[min] <= nums[mid]){ if(nums[min] <= target && target < nums[mid]){ max = mid - 1; } else { min = mid + 1; } // 如果右半部份是有序的 } else { if(nums[mid] < target && target <= nums[max]){ min = mid + 1; } else { max = mid - 1; } } } // 不满足min <= max条件时,返回-1 return -1; } }
递归写法
public class Solution { public int search(int[] nums, int target) { return helper(nums, 0, nums.length - 1, target); } public int helper(int[] nums, int min, int max, int target){ int mid = min + (max - min) / 2; // 不满足min <= max条件时,返回-1 if(min > max){ return -1; } if(nums[mid] == target){ return mid; } // 如果左半部分是有序的 if(nums[min] <= nums[mid]){ // 如果在左半部分的边界内 if(nums[min] <= target && target < nums[mid]){ return helper(nums, min, mid - 1, target); // 如果不在左半部分的边界内 } else { return helper(nums, mid + 1, max, target); } // 如果右半部份是有序的 } else { // 如果在右半部分的边界内 if(nums[mid] < target && target <= nums[max]){ return helper(nums, mid + 1, max, target); // 如果不在右半部分的边界内 } else { return helper(nums, min, mid - 1, target); } } } }Search in Rotated Sorted Array II
Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?二分法 复杂度Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
时间 O(N) 空间 O(1)
思路如果可能有重复,那我们之前判断左右部分是否有序的方法就失效了,因为可能有这种13111情况,虽然起点小于等于中间,但不代表右边就不是有序的,因为中点也小于等于终点,所有右边也是有序的。所以,如果遇到这种中点和两边相同的情况,我们两边都要搜索。
代码public class Solution { public boolean search(int[] nums, int target) { return helper(nums, 0, nums.length - 1, target); } public boolean helper(int[] nums, int min, int max, int target){ int mid = min + (max - min) / 2; // 不符合min <= max则返回假 if(min > max){ return false; } if(nums[mid] == target){ return true; } boolean left = false, right = false; // 如果左边是有序的 if(nums[min] <= nums[mid]){ // 看目标是否在左边有序数列中 if(nums[min] <= target && target < nums[mid]){ left = helper(nums, min, mid - 1, target); } else { left = helper(nums, mid + 1, max, target); } } // 如果右边也是有序的 if(nums[mid] <= nums[max]){ // 看目标是否在右边有序数列中 if(nums[mid] < target && target <= nums[max]){ right = helper(nums, mid + 1, max, target); } else { right = helper(nums, min, mid - 1, target); } } // 左右两边有一个包含目标就返回真 return left || right; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/64612.html
摘要:如正常的升序排列应该是,,,,,,旋转过后可能就是,,,,,,。想法因为这是一个经过旋转的升序数组,我们可以将其看作两个升序的序列,,,和,,。如果在前一个序列,则从前面进行查找。如果在后面一个序列,则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
摘要:这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。 题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 ...
摘要:二分迭代法复杂度时间空间递归栈空间思路找旋转数组的起点,实际上类似找一个山谷,只要两边都比中间高就对了,这和这题很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...
摘要:找中点若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无,就容易了。还是用二分法优化 Search in Rotated Sorted Array Problem Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 ...
摘要:题目要求相比于,中添加了数组中可能存在重复值的条件。这是我们可以将情况分为以下几种。因为如果而且,则左侧或右侧的子数组至少有一个为顺序的数组,这违背题目要求。所哟一定是同理,如果,那么。 题目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. ...
阅读 2042·2021-09-22 15:43
阅读 8377·2021-09-22 15:07
阅读 1058·2021-09-03 10:28
阅读 2028·2021-08-19 10:57
阅读 1026·2020-01-08 12:18
阅读 2958·2019-08-29 15:09
阅读 1499·2019-08-29 14:05
阅读 1585·2019-08-29 13:57