国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Find Minimum in Rotated Sorted Array

DataPipeline / 1756人閱讀

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

題目

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.

思路

個人覺得這是一道值得回味的二分法題目。與給出target的二分法搜索比,這道題目的target是未知的,并且array是rotated。我個人是從觀察給出的例子入手的。
通過觀察這個例子,我們發現以下特征:

最小值是唯一一個比它左右相鄰數字都小的數字

當中位數比start 和 end 都大的時候,最小值在右邊

當中位數比start 和 end 都小的時候,最小值在左邊

當中位數比start大,比end小的時候,我們進入了sorted的array,最小值也是在左邊

那么我們做這道題目的目的,就是通過2,3這兩步,進入最小值所在的sorted的array,從而進行第4步。我本人走的彎路是,過于專注于1,從而邏輯變得復雜。其實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]
體會

這道題目的個人體會就是如果用二分法處理sorted array,核心邏輯在于把已知input分為左右兩部分,再從中入手。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/40819.html

相關文章

  • [LintCode/LeetCode] Find Minimum in Rotated Sorted

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

    cgh1999520 評論0 收藏0
  • [Leetcode] Find Minimum in Rotated Sorted Array 找旋

    摘要:二分迭代法復雜度時間空間遞歸棧空間思路找旋轉數組的起點,實際上類似找一個山谷,只要兩邊都比中間高就對了,這和這題很像。 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 評論0 收藏0
  • leetcode153-154 find minimum rotated sorted array

    摘要:題目要求假設有一個升序排序的數組,在某個節點處斷開并調換了順序。尋找這個斷開數組中的最小元素。但是如果我們將頭尾的重復元素清楚,而只是在數組中間存在重復元素的話,如,這樣并不會影響升序數組位置的判斷。 題目要求 Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor...

    DrizzleX 評論0 收藏0
  • LeetCode 154 在有序旋轉數組中找最小-2

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

    evin2016 評論0 收藏0
  • LeetCode 153 在有序旋轉數組中找最小-1

    摘要:難度就是說一個從小到大排序好的數組循環移位不知多少次,求最小值。數組無重復值無重復的話就比較簡單,用二分查找即可。當前游標始終是左右游標中點位置,與左右游標的數值比較。解法有幾個要點基本終止條件為左邊的數比當前的數大,那么當前數即是最小值。 Question:Suppose a sorted array is rotated at some pivot unknown to you b...

    MkkHou 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<