C++實(shí)現(xiàn)尋找旋轉(zhuǎn)有序數(shù)組的最小值的方法

本篇內(nèi)容介紹了“C++實(shí)現(xiàn)尋找旋轉(zhuǎn)有序數(shù)組的最小值的方法”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

尋找旋轉(zhuǎn)有序數(shù)組的最小值

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.

Example 1:

Input: [3,4,5,1,2]
Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]
Output: 0

這道尋找旋轉(zhuǎn)有序數(shù)組的最小值肯定不能通過直接遍歷整個(gè)數(shù)組來尋找，這個(gè)方法過于簡(jiǎn)單粗暴，這樣的話，旋不旋轉(zhuǎn)就沒有意義。應(yīng)該考慮將時(shí)間復(fù)雜度從簡(jiǎn)單粗暴的 O(n) 縮小到 O(lgn)，這時(shí)候二分查找法就浮現(xiàn)在腦海。這里是比較難的那一類，沒有固定的 target 值比較，而是要跟數(shù)組中某個(gè)特定位置上的數(shù)字比較，決定接下來去哪一邊繼續(xù)搜索。這里用中間的值 nums[mid] 和右邊界值 nums[right] 進(jìn)行比較，若數(shù)組沒有旋轉(zhuǎn)或者旋轉(zhuǎn)點(diǎn)在左半段的時(shí)候，中間值是一定小于右邊界值的，所以要去左半邊繼續(xù)搜索，反之則去右半段查找，最終返回 nums[right] 即可，參見代碼如下：

解法一：

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = (int)nums.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) left = mid + 1;
            else right = mid;
        }
        return nums[right];
    }
};

下面這種分治法 Divide and Conquer 的解法，這里每次將區(qū)間 [start, end] 從中間 mid 位置分為兩段，分別調(diào)用遞歸函數(shù)，并比較返回值，每次取返回值較小的那個(gè)即可，參見代碼如下：

解法二：

討論：對(duì)于數(shù)組中有重復(fù)數(shù)字的情況，請(qǐng)參見另一篇博文 Find Minimum in Rotated Sorted Array II。

Github 同步地址：

https://github.com/grandyang/leetcode/issues/153

“C++實(shí)現(xiàn)尋找旋轉(zhuǎn)有序數(shù)組的最小值的方法”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！