leetcode-33-Search in Rotated Sorted Array

SKYZACK 發(fā)布于2019-07-30 17:19 / 983人閱讀

摘要：由于不是一直升序，所以需要多些條件進(jìn)行范圍的限定。注意邊界值的確定，有邊界值相等，列表只有一個(gè)值，這些情況。注意的使用應(yīng)用排序，快速確定某個(gè)值的位置

題目闡釋：

給定一組升序數(shù)組，取某個(gè)點(diǎn)之后將數(shù)組截?cái)嘟粨Q前后兩個(gè)數(shù)組順序，
給定一個(gè)值，求這個(gè)值的index

重點(diǎn)：二分法，確定target在哪個(gè)列表中，之后不斷二分法進(jìn)行位置確認(rèn)。

   由于不是一直升序，所以需要多些條件進(jìn)行范圍的限定。
   二分法，需要不斷 mid-1或者mid+1，因?yàn)閙id已經(jīng)判斷過(guò)，沒(méi)有再出現(xiàn)在數(shù)組的意義。  
   注意邊界值的確定，有 邊界值相等，列表只有一個(gè)值，這些情況。注意 <  <=的使用

應(yīng)用：排序，快速確定某個(gè)值的位置

class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        start,end=0,len(nums)-1
        # mid=(start+end)//2+1
        while True:
            mid=(start+end)//2
            if mid>end:
                return -1
            if nums[mid]==target:
                return mid
            if end<=start:
                return -1
            if nums[start]<=target<=nums[mid] or nums[mid]

GPU云服務(wù)器云服務(wù)器 sorted-array in_array() in_array in_array()函數(shù)

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/42148.html

相關(guān)文章

leetcode33 search in rotated sorted array

摘要：這里相比于思路一，更適用于目標(biāo)節(jié)點(diǎn)在中間的情況，而思路一在目標(biāo)節(jié)點(diǎn)分布在數(shù)組兩側(cè)會(huì)效率更高。題目要求 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 ...

MkkHou 2019-08-14 18:11 評(píng)論0 收藏0
leetcode 33 Search in Rotated Sorted Array

摘要：如正常的升序排列應(yīng)該是，，，，，，旋轉(zhuǎn)過(guò)后可能就是，，，，，，。想法因?yàn)檫@是一個(gè)經(jīng)過(guò)旋轉(zhuǎn)的升序數(shù)組，我們可以將其看作兩個(gè)升序的序列，，，和，，。如果在前一個(gè)序列，則從前面進(jìn)行查找。如果在后面一個(gè)序列，則從最后一個(gè)元素開(kāi)始查找。題目詳情 Suppose an array sorted in ascending order is rotated at some pivot unknown...

diabloneo 2019-08-16 11:04 評(píng)論0 收藏0
[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 2019-08-14 15:22 評(píng)論0 收藏0
Find Minimum in Rotated Sorted Array

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

DataPipeline 2019-07-30 14:38 評(píng)論0 收藏0
[Leetcode] Find Minimum in Rotated Sorted Array 找旋

摘要：二分迭代法復(fù)雜度時(shí)間空間遞歸棧空間思路找旋轉(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 2019-08-14 12:24 評(píng)論0 收藏0