LeetCode Find Minimum In Rotated Sorted Array

#include <iostream>

#include <cstdlib>

#include <vector>



using namespace std;

// 4 5 1 2

// 1 2

class Solution {

public:

    int findMin(vector<int> &num) {

        int len = num.size();

        if (len < 1) {

            // should not happened;

            return 0;

        }

        if (len == 1) {

            return num[0];

        } 

        int p = 0; 

        int q = len - 1;

        

        // array with no rotation

        if (num[p] < num[q]) {

            return num[p];

        }

        

        // array been rotated

        while (p + 1 < q) {

            int m = (p + q) / 2;

            if (num[m] > num[q]) {

                p = m;

            } else if (num[m] < num[q]){

                q = m;

            }

        }

        return num[q];

    }

};



int main() {



    //int arr[] = {4, 5, 6, 7, 0, 1, 2};

    //int arr[] = {1, 2, 3};

    int arr[] = {1, 2};

    //int arr[] = {2, 1};

    vector<int> array(arr, arr + sizeof(arr) / sizeof(int));

    

    Solution s;

    

    cout<<s.findMin(array)<<endl;    

    

    return 0;

}

 
第2ラウンド:
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 class Solution {

 2 public:

 3     int findMin(vector<int> &num) {

 4         int n = num.size();

 5         if (n < 1) {

 6             return INT_MIN;

 7         }

 8         if (n == 1) {

 9             return num[0];

10         }

11         int m = min(num[0], num.back());

12         

13         if (m == num[0]) {

14             return m;

15         }

16         

17         int p = -1;

18         int q = n;

19         while (p + 1 < q) {

20             int mid = (p + q) / 2;

21             if (num[mid] > m) {

22                 p = mid;

23             }  else {

24                 q = mid;

25             }

26         }

27         return num[q];

28     }

29 };

上记は烦わしすぎて、二分検索は実は下记の选択に対してやはりとても凝っていて、问题の中の解の要素のインデックスの空间は0にあるためです...n-1間なので、直接p=0、q=n-1とすればよい.純粋な二分探索であれば初期p=0,q=n(実はlower_boundの初期)が一般的ですが、要素は0ではない可能性があるので...n-1間.

 1 class Solution {

 2 public:

 3     int findMin(vector<int>& nums) {

 4         int len = nums.size();

 5         int p = 0, q = len - 1;

 6         while (p < q) {

 7             int mid = (p + q) / 2;

 8             if (nums[mid] > nums[q]) {

 9                 p = mid + 1;

10             } else {

11                 q = mid;

12             }

13         }

14         return nums[p];

15     }

16 };