0%

leetcode每日一题-旋转数组的最小数字

Posted on Edited on In ,

旋转数组的最小数字

image1

方法一

可以通过旋转数组的性质，寻找第一个小于前继数的数，该数就是最小数。

1
class Solution {
2
    public int minArray(int[] numbers) {
3
        if(numbers.length == 1){
4
            return numbers[0];
5
        }
6
        int prev = numbers[0];
7
        for(int i=1; i<numbers.length; i++){
8
            if(prev <= numbers[i]){
9
                numbers[i] = prev;
10
                continue;
11
            }else{
12
                return numbers[i];
13
            }
14
        }
15
        return numbers[0];
16
    }
17
}

复杂度分析：

  • 时间复杂度：$O(n)$。
  • 空间复杂度：$O(1)$。

方法二：二分查找

考虑旋转数组最后一个数$x$，小于等于$x$的都在数组中最小数的右边，大于等于$x$的都在数组中最小数的左边。那么可以利用此性质进行二分查找。

  1. 如果中间数mid大于high，那么说明最小数在mid的右边，那么将low改为mid+1。
  2. 如果中间数mid小于high，那么说明最小数在mid的左边，那么将high改为mid。
  3. 如果中间数mid等于high，那么说明最小数有可能在mid的左边，也有可能在右边，那么将high减一逐渐逼近。
1
class Solution {
2
    public int minArray(int[] numbers) {
3
        int low = 0;
4
        int high = numbers.length-1;
5
        while(low < high){
6
            int mid = low + (high-low)/2;
7
            if(numbers[mid] < numbers[high]){
8
                high = mid;
9
            }else if(numbers[mid] > numbers[high]){
10
                low = mid+1;
11
            }else{
12
                high--;
13
            }
14
        }
15
        return numbers[low];
16
    }
17
}

复杂度分析：

  • 时间复杂度：$O(logn)$。
  • 空间复杂度：$O(1)$。