アルゴリズム学習(五)

アルゴリズム#学習目標:二分法

学習内容:

学習産出:

開方

を求める

LeetCode 69 xの平方根

題解

コード(python)

探索区間

LeetCode 34は、ソート配列内の要素の最初の位置と最後の位置を検索する

題解

コード(python)

回転配列

LeetCode 81回転ソート配列II

を検索する

題解

コード(python)

学習内容:
二分法:検索ごとに検索区間を二つに分けて一部だけ検索することで、検索の複雑度を減少させ、n長の区間に対して時間複雑度をO(logn)とする
学習産出:
開方、探索区間、回転配列を求めます
処方を求める.
LeetCode 69 xの平方根
int sqrt(int x)関数を実現します.
xの平方根を計算して返します.ここで、xは非負の整数です.
戻りタイプが整数であるため、結果として整数の部分のみが保持され、小数の部分は切り捨てられます.

   1:

  : 4
  : 2

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/sqrtx
          。           ，          。

問題解
問題を一元二次方程式解として想像し,f(x)=x 2−a=0,x>=0 f(x)=x^{2}−a=0,x>=0 f(x)=x=x=x−x−a=0,x>=0の解であるため,f(x)f(x)f(x)f(x)f(x)f(x)f(x)は定義域で単調に増加し,f(0)=−a<0,f(a)=a 2−a<0,f(a)=a 2−a>0 f(0)=−a<0,f(a)=a^{2}−a>0 f(0)=a(0)=a(0)=a<0,f(0)=a<0)=a,f(a)=a 2−a>0であるため,区間を[0,a]と考え,[0,a]区間のf(x)=0 f(x)=0 f(x)=0の解を二分法で検索する
手順:

初期化左右区間

二分取区間中間数

の中間が大きい場合は、小さな左部分をとる.中間が小さい場合は、大きい右部分

をとる.

結果

が得られるまで、第2および第3のステップを繰り返す.
コード(python)

class Solution:
    def mySqrt(self, x: int) -> int:
    	if x == 0: return 0
    	l,r = 0,x #     [l,r]
    	while l <= r :
    		mid = (l+r)/2  #    
    		if x < mid * mid:  #    ，       
    			r = mid - 1
    		elif x > mid * mid: #    ，       
    			l = mid + 1
    		else:
    			return mid
    	return r

実はニュートン反復法を考えることができて、もっと簡単です(詳しく紹介しません)

class Solution:
    def mySqrt(self, x: int) -> int:
    	a = x
    	while a * a > x:
    		x = (x+a/x)/2
    	return x

サーチ区間
LeetCode 34は、ソート配列内の要素の最初の位置と最後の位置を検索する
昇順に配列された整数配列numsと、ターゲット値targetが与えられる.配列内の所定のターゲット値の開始位置と終了位置を特定します.
配列にターゲット値targetが存在しない場合は、[-1,-1]を返します.
ステップ:
時間的複雑度O(log n)のアルゴリズムを設計し実現してこの問題を解決できますか?

   1：

  ：nums = [5,7,7,8,8,10], target = 8
  ：[3,4]

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
          。           ，          。

問題解
二分検索で、重複する数値の左右の境界を検索します.
手順:

初期化左右区間

二分取区間中間数

左区間

を検索

は、結果

が得るまで、第2および第3のステップを繰り返し、右区間を探索する.
コード(python)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        #     ，      
        if not nums:
            return [-1, -1]
        return [self.search_left(nums, target), self.search_right(nums, target)]

    def search_left(self, nums, target): #     
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            elif nums[mid] == target:
                r = mid - 1        #           
        if l >= len(nums) or nums[l] != target:   #         
            return -1
        return l

    def search_right(self, nums, target): #     
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] > target:
                r = mid - 1
            elif nums[mid] < target:
                l = mid + 1
            elif nums[mid] == target:
                l = mid + 1        #           
        if r < 0 or nums[r] != target:   #         
            return -1                                   
        return r

python内蔵関数index実装,複雑度O(1),反転リストO(n)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if target not in nums:return [-1,-1]
        i = nums.index(target)
        j = len(nums)-nums[::-1].index(target)
        return [i,j-1]
            

かいてんはいれつ
LeetCode 81は、回転ソート配列IIを検索する
昇順で並べ替えられた配列が予め未知の点で回転していると仮定する.
(例えば、配列[0,0,1,2,2,5,6]は[2,5,6,0,0,1,2]になる可能性がある).
与えられたターゲット値が配列に存在するかどうかを判断する関数を作成します.戻りtrueがある場合はfalseを返します.

  : nums = [2,5,6,0,0,1,2], target = 0
  : true

  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii
          。           ，          。

問題解
配列は回転され、依然として配列の増加性を借りて、二分法で中点を取り、中点が右端以下であれば、右区間の順序を説明する.そうでなければ、左区間は順番に並べられます.ターゲット値がソートされた区間内にある場合は、二分法で検索します.そうでなければ、別の区間を検索します.注意:重複データが発生した場合は、左端に1桁右に移動します.
手順:

初期化左右区間

二分取区間中間数

左区間

を検索

は、結果

が得るまで、第2および第3のステップを繰り返し、右区間を探索する.
コード(python)

class Solution:
    def search(self, nums: List[int], target: int) -> bool:
        l,r = 0,len(nums)-1
        while l <= r:
        	mid = (l + r) // 2
        	if nums[mid] == target : return True
        	if nums[l] == nums[mid] :  #            
        		l+=1
        	elif nums[mid] <= nums[r]: #     
        		if target > nums[mid] and target <= nums[r]:  #   
        			l = mid + 1
        		else:
        			r = mid - 1
        	else: #     
        		if target >= nums[l] and target <= nums[mid]:  #   
        			r = mid - 1
        		else:
        			l = mid + 1
        return False  		
            		

python内蔵関数indexはより簡単に実現でき、複雑度O(1)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        try:
            nums.index(target)
            return True
        except:
            return False