pythonによるleetcode 33の回転ソート配列の検索

920 ワード
lettecode 中ぐらい
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば配列[0,1,2,4,5,6,7]は[4,5,6,7,0,1,2]になる可能性がある).
指定したターゲット値を検索し、配列にターゲット値が存在する場合はインデックスを返します.そうでない場合は-1を返します.
配列に重複する要素が存在しないと仮定できます.
あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.
例1:
入力:nums=[4,5,6,7,0,1,2]、target=0出力:4例2:
入力:nums=[4,5,6,7,0,1,2],target=3出力:-1構想はまずどこで回転が発生したかを検出し,n=len(nums)/2 nums[n]>nums[0]のとき,前半部分が秩序化されていない場合,後半部分が秩序化されているかどうかを検出し,targetが秩序化されている部分の中にあるか,すなわち最大の要素以下であるか,または最小の要素よりも小さい場合は,必ず別の部分でコードを検出する
def search(self, nums, target):
        if(len(nums)<=5):
            if target in nums:return nums.index(target)
            return -1
        n=len(nums)//2
        if(nums[n]>nums[0]):
            if(nums[n]<=target or targettarget or nums[-1]
yapfの列幅制限値の変更
k-近隣アルゴリズム(kNN)