leetcode153-154.Find Minimum Rotated Sorted Array

发表于 更新于 分类于 ，

题目要求

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).

Find the minimum element.

假设有一个升序排序的数组，在某个节点处断开并调换了顺序。寻找这个断开数组中的最小元素。

当数组中不存在重复的元素

通过二分法来实现在logN的时间中找到最小的值。通过二分法往往会有以下几种情况

  1. 位于一个升序的数组中，也就是左侧值小于右侧值，这时候左侧值就是最小值。
  2. 左侧值小于中间值，那么中间值左侧一定是升序数组，所以最小值在右侧
  3. 中间值小于右侧值，那么中间值右侧一定是升序数组，所以最小值要么在左侧，要么就是中间值

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findMin(int[] nums) {
    int leftPointer = 0;
    int rightPointer = nums.length-1;
    while(leftPointer<rightPointer){
        if(nums[leftPointer]<nums[rightPointer]){
            break;
        }else{
            int mid = (leftPointer + rightPointer) / 2;
            if(nums[leftPointer]<nums[mid]){
                leftPointer = mid+1;
            }else if(nums[mid]<nums[rightPointer]){
                rightPointer = mid;
            }else{
                leftPointer++;
            }
            
        }
    }
    return nums[leftPointer];
}

数组中存在重复的元素

唯一会影响遍历的是数组的开头和结尾处的元素为重复元素，如[4,4,1,4,4]，在这种情况下就无法通过上面一种方法来识别出升序数组位于中间值的左侧或是右侧。但是如果我们将头尾的重复元素清楚，而只是在数组中间存在重复元素的话，如[4,1,1,1,3]，这样并不会影响升序数组位置的判断。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int findMin2(int[] nums) {
    if (nums == null || nums.length == 0) {
        return Integer.MIN_VALUE;
    }
    
    int start = 0, end = nums.length - 1;
    
    while (nums[end] == nums[start] && end > start) {
        end--;
    }
    
    while (start < end) {
        if (nums[start] < nums[end]) {
            return nums[start];
        }
        
        int mid = start + (end - start) / 2;
        if (nums[mid] >= nums[start]) {
            start = mid + 1;
        }
        else {
            end = mid;
        }
    }
    
    return nums[start];
}