LeetCode

LeetCode-153-找到最小值

二分查找。

  • 描述：

    一个递增序列，中间某个位置切一刀，之后前后两部分交换位置。找到此时的最小值。如[4,5,6,7,0,1,2]返回0。

  • 思路：

    两种情况：

    第一，数组中没有重复元素时，此情况容易，当这一刀没有切，数组递增，第一个元素为最小值。如果切下去了，那么最小值应该在数组切面处，如上述例子，切面在7和0，而最小值就在切面处。所以接下来的步骤就是二分查找法找切面。

    第二，数组中含有重复元素，此时情况较多，需要将所有情况都找到，较困难，这里是别人的如何找到所有情况的方法。

  • 实现：

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    // 不含重复元素
    int findMin(vector<int>& nums) {
        if(nums.size()==1) return nums[0];
        int head = 0;
        int tail = nums.size()-1;
        // 如果这一刀没有切
        if (nums[head] < nums[tail])
            return nums[head];

        while(head <= tail){
            int mid = head+(tail-head)/2;
            // 找到切面
            if(nums[mid] > nums[mid+1])
                return nums[mid+1];
            if(nums[mid-1] > nums[mid])
                return nums[mid];
            
            // 没有找到切面
            if(nums[mid] > nums[head])
                head = mid+1;
            else if(nums[mid] < nums[head])
                tail = mid-1;
        }
        return -1; 
    }   
    // 含重复元素
    int findMin(vector<int>& nums){
        int head=0;
        int tail=nums.size()-1;
        int mid; 
        while(head<=tail ){
            mid = head+(tail-head)/2;
            if(head==mid || mid==tail)
                return min(min(nums[head], nums[mid]), nums[tail]);
            if(nums[head]<=nums[mid] && nums[mid]<=nums[tail])
                tail--;
            else if(nums[mid]<=nums[tail] && nums[tail]<=nums[head])
                tail = mid; 
            else if(nums[tail]<=nums[head] && nums[head]<=nums[mid])
                head = mid; 
        }
        return -1; 
    }   
};