Rotated Sorted Array Related

Leave a comment

September 30, 2016 by oneOokay

  • Find Minimum in Rotated Sorted Array I
  • Find Minimum in Rotated Sorted Array II
  • Search in Rotated Sorted Array I
  • Search in Rotated Sorted Array II

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 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

Notice: You may assume no duplicate exists in the array.

Find Minimum in Rotated Sorted Array II:

Notice: The array may contain duplicates.

rotated array的话,一定会有一段会是单调增的.也要注意array也可能rotated了刚好整数倍.

模板:

while(start < end){
start = mid + 1;
end = mid;
}
返回的[start,end]:start为最小值,end为最大值.

I 的解法1是有一个数学理论:

  • 把中点和end相比较,如果中点值>end值的话,说明这个array肯定是被rotated了,且最小值肯定存在于[mid, end]之间
public int findMin(int[] nums) {
        int start = 0; 
        int end = nums.length - 1;
        int mid = 0;
        while (start < end){
            mid = start + (end - start) / 2;
            if (nums[end] < nums[mid]) 
start = mid + 1;
            else end = mid;
        }
        return nums[start];
    }

解法2:找到单调增的那个区间:

  • 如何找到,将start,mid和end的值进行对比.
  • 画一个图, 两端线段,竖着画一条代表中线:考虑中线落在左边的线段上的情况,这个时候[start, mid]就是一个单调增区间;中线落在右边的线段上,这个时候[mid, end]就是一个单调增区间.
public int findMin(int[] nums) {
 int start = 0; 
 int end = nums.length - 1;
 int mid = 0;
 while (start < end){
 mid = start + (end - start) / 2;
 if (nums[start] < nums[mid]){
//中线落在左边线段,左边递增,最小值位于中线右边
 if (nums[mid] > nums[end]) start = mid + 1;
 else end = mid;
 }else {
//起点值大于中点值且中点值小于终点值:中线落在右边线段上,
右边递增,最小值位于中线左边.
 if (nums[mid] < nums[end]) end = mid;
 else start = mid + 1;
 } }
return nums[start];
 }

II 存在重复的值,所以很可能中点与起点和终点都一样。以及最坏情况是n-1个值都一样,只有一个值是不同的。

  • 把mid和end相比.如果mid和end相等,end–.其余逻辑不变.
public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        int mid = 0;
        while (start < end){
             mid = start + (end - start) / 2;
             if (nums[mid] == nums[end]) end --; 
            else if (nums[mid] > nums[end]) 
                  start = mid + 1;
            else end = mid;
        }
        return nums[start];
    }

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.


关键点也是在于找到单调增区间.两种方法:

  1. 先找到最小值来找到rotate了多少,然后从最小值开始正常的binary search.
  2. 找到过程中确定递增区间.
    1. 注意确定mid处于哪个递增区间的时候,是把start和mid以及mid和end进行比较,并不涉及target.
    2. 确定好了递增区间之后,如果mid是在左递增区间,那么对start,target以及target和mid必须同时满足递增条件,才可确定,我们要找的target在左递增区间内,从而end = mid – 1. 其他时候target就在mid的右边了;
    3. 而且要注意start + (end – start) / 2的mid的算法是靠近start的,会存在start == mid的情况. 所以确定区间的时候,左递增区间是包含start <= mid的
 public int search(int[] nums, int target) {
 if (nums == null || nums.length == 0) return -1;
 int start = 0;
 int end = nums.length - 1;
 int mid = 0;
 while (start < end){
 mid = start + (end - start) / 2;
 if (nums[mid] == target) return mid;
 if (nums[start] <= nums[mid]){//这里是<=. 确定了mid是处于做左线段上.
//同时对start, target和mid进行判断,只有当两个条件同时满足才可以.
//也要注意nums[start] <= target
 if (nums[start] <= target && target < nums[mid]) 
end = mid;
 else 
start = mid + 1;//target在mid右边.
 }else {//start < mid说明mid在右边的线段上.
//也是同时要对三个mid,target和end的值进行判断,只有同时满足才可以.
//也要注意target 是可能<= nums[end]的
 if (nums[mid] < target && target <= nums[end]) 
start = mid + 1;
 else end = mid;//target在mid的左边
 }
 }
 return nums[start] == target ? start : -1;
 }

Search in Rotated Sorted Array II:

九章:http://www.jiuzhang.com/solutions/search-in-rotated-sorted-array-ii/。
也就是如果是最坏情况的话跟Find Minimum in Rotated Sorted ArrayII 情况一样,用一个for-loop就可以了,因为这种情况下用binary search的时间复杂度和for-loop的时间复杂度是一样的。
写了一个binary search的方法:结合Find Minimum in Rotated Sorted ArrayII 和Search In Rotated Sorted ArrayI:当mid == end的时候,end –;只把mid和end进行比较,然后再在其中找到单调增区域
public boolean search(int[] A, int target) {
if (A == null || A.length == 0) {
return false;
}int start = 0;
int end = A.length – 1;while (start + 1 < end) {
int mid = start + (end – start) / 2;
if (A[mid] == target) {
return true;
}if (A[mid] == A[end]) {
end –;
}else if (A[mid] < A[end]) { //mid在右上升段
if (A[mid] < target && target <= A[end]){ //mid, target, end 依次递增
start = mid;
}else {
end = mid;
}
}else { //A[mid] > A[end] mid在左上升段
if (A[start] <= target && target < A[mid]) { //start, target mid依次递增
end = mid;
}else {
start = mid;
}}}if (A[start] == target || A[end] == target) {
return true;
}
return false;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: