剑指 Offer 11. 旋转数组的最小数字

https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

解法一：
暴力法，直接遍历一遍数组，找出其中的最大值即可

class Solution {
    public int minArray(int[] numbers) {
        int min=Integer.MAX_VALUE;
        for(int number:numbers){
            if(number<min){
                min=number;
            }
        }
        return min;
    }
}
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int min=INT_MAX;
        for(int num:numbers){
            if(num<min){
                min=num;
            }
        }
        return min;
    }
};
//O(n)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        min=10000
        for num in numbers:
            if num<min:
                min=num
        return min
1
2
3
4
5
6
7

解法二： 二分查找

对于旋转后的数字，虽然数组整体不是有序的，但是数组的分为两部分，这两部分一定是各自有序的，以numbers = [3,4,5,1,2]为例，3 4 5是升序的，1 2是升序的，即数组分为两部分有序，分别称为左半部分有序和右边部分有序, 最小的数字是右半部分的第一个数字

最右边的数字一定属于右半部分有序，将最右边的元素nums[r]和中间元素num[mid]进行比较，分为以下3种情况：

1. nums[r]
2. nums[r]>nums[mid]: mid属于右半部分有序，最小数字属于区间[left,mid] mid可能是最小数字，因此区间包含mid
3. nums[r]==nums[mid]: 由于数组中存在重复元素， 此时不直接返回，而是缩小右边界

这里不和nums[i]进行比较的原因是因为最开始的最左边的元素nums[i]并不能确定其属于左半部分有序数组还是右半部分有序数组

class Solution {
    public int minArray(int[] numbers) {
        int left=0,right=numbers.length-1;
        while(left<right){
            int mid=left+(right-left)/2;
            if(numbers[mid]>numbers[right]){
                left=mid+1;
            }else if(numbers[mid]<numbers[right]){
                right=mid;
            }else if(numbers[mid]==numbers[right]){
                right--;
            }
        }
        return numbers[left];
    }
}
//O(logn)
//O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int l=0,r=numbers.size()-1;
        while(l<r){
            int m=l+(r-l)/2;
            if(numbers[m]>numbers[r]){
                l=m+1;
            }else if(numbers[m]<numbers[r]){
                r=m;
            }else if(numbers[m]==numbers[r]){
                r--;
            }
        }
        return numbers[l];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left=0
        right=len(numbers)-1
        while left<right:
            mid=left+(right-left)//2
            if numbers[mid]>numbers[right]:
                left=mid+1
            elif numbers[mid]<numbers[right]:
                right=mid
            elif numbers[mid]==numbers[right]:
                right-=1
        return numbers[left]
1
2
3
4
5
6
7
8
9
10
11
12
13