LeetCode-153

发表于   |   分类于   |  

Find Minimum in Rotated Sorted Array

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.

You may assume no duplicate exists in the array.

题目大意：

据提交后了解到：

  1. 该数组实在单调递增的情况下的
  2. 该数组可能就是单调递增的，也可能是在某个节点旋转了。

解题思路：

  1. 看到排序，然后又要查找，一般就是二分查找法。

解体答案：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//O(lgn)
public class Solution {
    public int findMin(int[] num) {
      int len = num.length;  
        if (len == 1) return num[0];  
        int left = 0, right = len-1;  
        while (num[left] > num[right]) { // good idea  
            int mid = (left + right) / 2;  
            if (num[mid] > num[right]) {  
                left = mid + 1;  
            } else {  
                right = mid; // be careful, not mid-1, as num[mid] maybe the minimum  
            }  
        }  
        return num[left];  
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
\\O(lgn) not good enough
public int findMin1(int[] num) {
int len = num.length;  
        if (len == 1) {  
            return num[0];  
        }  
          
        for (int i = 1; i < len; i++) {  
            if (num[i] < num[i-1]) {  
                return num[i];  
            }  
        }  
          
        return num[0]; 
  }