leetcode 153. Find Minimum in Rotated Sorted Array 旋转数组（不重复）+二分查找

Myth丶恋晨 2022-06-08 06:28 150阅读 0赞

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.

You may assume no duplicate exists in the array.

我的做法就是找到转折点，然后就可以得到答案了。

代码如下：

/*
     * 我的解决办法是最简单粗暴的，直接寻找转折点即可
     * 
     * */
    public class Solution 
    {
        public int findMin(int[] nums) 
        {
            if(nums==null || nums.length<=0 )
                return 0;
    
            int min=nums[0];
            for(int i=1;i<nums.length;i++)
            {
                if(nums[i]>nums[i-1])
                    continue;
                else
                {
                    min = Math.min(min, nums[i]);
                    break;
                }
            }
            return min;
        }
    }

下面是C++的做法，就是做一次遍历寻找转折点

首先要判断这个有序数组是否旋转了，通过比较第一个和最后一个数的大小，如果第一个数小，则没有旋转，直接返回这个数。如果第一个数大，就要进一步搜索。我们定义left和right两个指针分别指向开头和结尾，还要找到中间那个数，然后和left指的数比较，如果中间的数大，则继续二分查找右半段数组，反之查找左半段。终止条件是当左右两个指针相邻，返回小的那个。

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int findMin(vector<int>& a)
        {
            if (a.size() <= 0)
                return 0;
            int left = 0, right = a.size()-1;
            if (a[left] <= a[right])
                return a[left];
            while (left != right - 1)
            {
                int mid = (right - left) / 2 + left;
                if (a[left] < a[mid])
                    left = mid;
                else
                    right = mid;
            }
            return min(a[left], a[right]);
        }
    };