摘要:这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。
题目要求
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 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.
翻译过来就是说:一个由小到大有序排列的数组被分为两个子数组,这两个子数组调换前后顺序生成一个新数组。在新数组中找到目标值并返回下标
思路一:双指针左右同时比较,直至找到目标值或是左右指针相遇
public int search(int[] nums, int target){ int left = 0; int right = nums.length - 1; while(left<=right){ if(nums[left]==target){ return left; } if(nums[right] == target){ return right; } left++; right--; } return -1; }思路二:二分法查找
思路一并没有充分利用条件,及这个数组是由两个有序的子数组合成的。这里我们可以使用二分法的一个变形的算法。先找到中间节点,这个中间节点如果不是在左顺序子数组,就一定在右顺序子数组,反之亦成立。这样我们就可以变相的使用二分法将区间范围逐渐缩小,直至找到目标值。
这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。
public int search(int[] nums, int target){ int left = 0; int right = nums.length - 1; while(left<=right){ int mid = (left + right)/2; int midNum = nums[mid]; if(midNum==target){ return mid; } if(nums[left]<=midNum){ if(nums[left]<=target && midNum>target){ right = mid - 1; }else{ left = mid + 1; } } if (midNum <= nums[right]){ if (target > midNum && target <= nums[right]) left = mid + 1; else right = mid - 1; } } return -1; }
想要了解更多开发技术,面试教程以及互联网公司内推,欢迎关注我的微信公众号!将会不定期的发放福利哦~
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/67054.html
摘要:如正常的升序排列应该是,,,,,,旋转过后可能就是,,,,,,。想法因为这是一个经过旋转的升序数组,我们可以将其看作两个升序的序列,,,和,,。如果在前一个序列,则从前面进行查找。如果在后面一个序列,则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
摘要:由于不是一直升序,所以需要多些条件进行范围的限定。注意边界值的确定,有边界值相等,列表只有一个值,这些情况。注意的使用应用排序,快速确定某个值的位置 题目阐释: 给定一组升序数组,取某个点之后将数组截断交换前后两个数组顺序, 给定一个值,求这个值的index 重点:二分法,确定target在哪个列表中,之后不断二分法进行位置确认。 由于不是一直升序,所以需要多些条件进行范围的限定...
摘要:如果左边的点比右边的大,说明这两个点之间有一个旋转点,导致了不再有序。因为只有一个旋转点,所以一分为二后,肯定有一半是有序的。 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 mi...
摘要:找中点若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无,就容易了。还是用二分法优化 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. ...
阅读 3312·2021-11-22 14:44
阅读 2522·2019-08-30 14:10
阅读 2562·2019-08-30 13:12
阅读 1188·2019-08-29 18:36
阅读 1324·2019-08-29 16:16
阅读 3293·2019-08-26 10:33
阅读 1739·2019-08-23 18:16
阅读 360·2019-08-23 18:12