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. 先找到最小值来确定递增区间
  2. 找到过程中确定递增区间,同找到最小值的方法

 

 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]){
 if (nums[start] <= target && target < nums[mid]) end = mid;
 else start = mid + 1;
 }else {
 if (nums[mid] < target && target <= nums[end]) start = mid + 1;
 else end = 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: