摘要:找中点若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。在左右半段分别进行二分法的操作。只判断有无,就容易了。还是用二分法优化
Search in Rotated Sorted Array Problem
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.
ExampleFor [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1.
ChallengeO(logN) time
Note找中点:若起点小于中点,说明左半段没有旋转,否则说明右半段没有旋转。
在左右半段分别进行二分法的操作。
public class Solution { public int search(int[] A, int target) { int start = 0, end = A.length-1, mid = 0; while (start <= end) { mid = (start+end)/2; if (A[mid] == target) return mid; if (A[start] <= A[mid]) { if (A[start] <= target && target <= A[mid]) end = mid-1; else start = mid+1; } else { if (A[mid] < target && target <= A[end]) start = mid+1; else end = mid-1; } } return -1; } }Search in Rotated Sorted Array II Problem
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.
Note只判断有无,就容易了。
Solution还是用二分法优化
public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; int start = 0, end = nums.length-1; while (start <= end) { int mid = start+(end-start)/2; if (nums[mid] == target || nums[start] == target || nums[end] == target) return true; if (nums[start] < nums[mid]) { if (nums[start] <= target && target < nums[mid]) end = mid-1; else start = mid+1; } else if (nums[start] > nums[mid]) { if (nums[mid] < target && target <= nums[end]) start = mid+1; else end = mid-1; } else { if (nums[start] != target) start++; if (nums[end] != target) end--; } } return false; } }Updated 2018-08
class Solution { public boolean search(int[] nums, int target) { int start = 0, mid = 0, end = nums.length-1; while (start <= end) { mid = start+(end-start)/2; if (nums[mid] == target || nums[start] == target || nums[end] == target) return true; if (nums[start] < nums[mid]) { if (nums[start] < target && target < nums[mid]) end = mid-1; else start = mid+1; } else if (nums[start] > nums[mid]) { if (nums[mid] < target && target < nums[end]) start = mid+1; else end = mid-1; } else { start++; end--; } } return false; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/65939.html
摘要:排序数组中找最小值或最大值的题目,很明显可以使用二分法。因此,只判断终点和中点元素的大小关系即可。这里有一种情况是上述后三个,中点值和末位相等。此时,两边同时递归,并返回两边递归值的较小值。当首位和末位重合,说明已夹逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...
摘要:如果左边的点比右边的大,说明这两个点之间有一个旋转点,导致了不再有序。因为只有一个旋转点,所以一分为二后,肯定有一半是有序的。 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...
摘要:这里相比于思路一,更适用于目标节点在中间的情况,而思路一在目标节点分布在数组两侧会效率更高。 题目要求 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 ...
摘要:如正常的升序排列应该是,,,,,,旋转过后可能就是,,,,,,。想法因为这是一个经过旋转的升序数组,我们可以将其看作两个升序的序列,,,和,,。如果在前一个序列,则从前面进行查找。如果在后面一个序列,则从最后一个元素开始查找。 题目详情 Suppose an array sorted in ascending order is rotated at some pivot unknown...
Problem Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume NO duplicates in the a...
阅读 3315·2021-11-12 10:36
阅读 2467·2021-11-02 14:43
阅读 2146·2019-08-30 14:23
阅读 3462·2019-08-30 13:08
阅读 919·2019-08-28 18:09
阅读 3129·2019-08-26 12:22
阅读 3140·2019-08-23 18:24
阅读 2016·2019-08-23 18:17