成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

Find Minimum in Rotated Sorted Array

DataPipeline / 1767人閱讀

摘要：題目思路個(gè)人覺(jué)得這是一道值得回味的二分法題目。與給出的二分法搜索比，這道題目的是未知的，并且是。我個(gè)人是從觀察給出的例子入手的。我本人走的彎路是，過(guò)于專注于，從而邏輯變得復(fù)雜。其實(shí)，，和步就可以幫助我們順利找到最小值。

題目

http://www.lintcode.com/en/pr...

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.

思路

個(gè)人覺(jué)得這是一道值得回味的二分法題目。與給出target的二分法搜索比，這道題目的target是未知的，并且array是rotated。我個(gè)人是從觀察給出的例子入手的。
通過(guò)觀察這個(gè)例子，我們發(fā)現(xiàn)以下特征：

最小值是唯一一個(gè)比它左右相鄰數(shù)字都小的數(shù)字

當(dāng)中位數(shù)比start 和 end 都大的時(shí)候，最小值在右邊

當(dāng)中位數(shù)比start 和 end 都小的時(shí)候，最小值在左邊

當(dāng)中位數(shù)比start大，比end小的時(shí)候，我們進(jìn)入了sorted的array，最小值也是在左邊

那么我們做這道題目的目的，就是通過(guò)2，3這兩步，進(jìn)入最小值所在的sorted的array，從而進(jìn)行第4步。我本人走的彎路是，過(guò)于專注于1，從而邏輯變得復(fù)雜。其實(shí)2，3，和4步就可以幫助我們順利找到最小值。

代碼 
class Solution:
    # @param nums: a rotated sorted array
    # @return: the minimum number in the array
    def findMin(self, nums):
        # write your code here
        if nums is None or len(nums) == 0:
            return -1
        start = 0
        end = len(nums) - 1
        while start + 1 < end:
            mid = start + (end - start) / 2
            if nums[mid] > nums[end]:
                start = mid
            elif nums[mid] < nums[start] or (nums[mid] < nums[end] and nums[mid] > nums[start]):
                end = mid
        return nums[start] if nums[start] < nums[end] else nums[end]
體會(huì)

這道題目的個(gè)人體會(huì)就是如果用二分法處理sorted array，核心邏輯在于把已知input分為左右兩部分，再?gòu)闹腥胧帧?/p>

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/40819.html

相關(guān)文章

  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

    摘要：排序數(shù)組中找最小值或最大值的題目，很明顯可以使用二分法。因此，只判斷終點(diǎn)和中點(diǎn)元素的大小關(guān)系即可。這里有一種情況是上述后三個(gè)，中點(diǎn)值和末位相等。此時(shí)，兩邊同時(shí)遞歸，并返回兩邊遞歸值的較小值。當(dāng)首位和末位重合，說(shuō)明已夾逼得到最小值。 Find Minimum in Rotated Sorted Array Problem Suppose a sorted array is rotated...

    cgh1999520 評(píng)論0 收藏0

  • [Leetcode] Find Minimum in Rotated Sorted Array 找旋

    摘要：二分迭代法復(fù)雜度時(shí)間空間遞歸?？臻g思路找旋轉(zhuǎn)數(shù)組的起點(diǎn)，實(shí)際上類似找一個(gè)山谷，只要兩邊都比中間高就對(duì)了，這和這題很像。 Find Minimum in Rotated Sorted Array I Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 ...

    notebin 評(píng)論0 收藏0

  • leetcode153-154 find minimum rotated sorted array

    摘要：題目要求假設(shè)有一個(gè)升序排序的數(shù)組，在某個(gè)節(jié)點(diǎn)處斷開(kāi)并調(diào)換了順序。尋找這個(gè)斷開(kāi)數(shù)組中的最小元素。但是如果我們將頭尾的重復(fù)元素清楚，而只是在數(shù)組中間存在重復(fù)元素的話，如，這樣并不會(huì)影響升序數(shù)組位置的判斷。 題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...

    DrizzleX 評(píng)論0 收藏0

  • LeetCode 154 在有序旋轉(zhuǎn)數(shù)組中找最小-2

    摘要：難度就是說(shuō)一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。比如全部是的數(shù)列，和除了某位置有個(gè)，其余全部是的數(shù)列，都是合法的。在這里，測(cè)試用例也進(jìn)行了增加，盡量覆蓋各種奇葩情況。 Follow up for Find Minimum in Rotated Sorted Array:What if duplicates are allowed?Would this affect th...

    evin2016 評(píng)論0 收藏0

  • LeetCode 153 在有序旋轉(zhuǎn)數(shù)組中找最小-1

    摘要：難度就是說(shuō)一個(gè)從小到大排序好的數(shù)組循環(huán)移位不知多少次，求最小值。數(shù)組無(wú)重復(fù)值無(wú)重復(fù)的話就比較簡(jiǎn)單，用二分查找即可。當(dāng)前游標(biāo)始終是左右游標(biāo)中點(diǎn)位置，與左右游標(biāo)的數(shù)值比較。解法有幾個(gè)要點(diǎn)基本終止條件為左邊的數(shù)比當(dāng)前的數(shù)大，那么當(dāng)前數(shù)即是最小值。 Question:Suppose a sorted array is rotated at some pivot unknown to you b...

    MkkHou 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<