CodeKata #2

3896 ワード
WeCode codekata テキストリンク
質問:
数値nums配列の昇順と検索するtargetをパラメータとすると、
targetはいくつかのindexです.戻ってください.
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
説明:見つからない場合は、-1に戻ってください.
nums配列の要素に重複値はありません

問題解決

  • 今回はバイナリ探索を学び、それを利用して解決します.
  • の昇順なので、まず中央値
    • をチェック
    検索する数字がもっと大きい場合は、リストの右側に表示されます.逆方向に検索する数値が小さい場合は、リストの左側に表示されます.
  • リストを2つの部分に分ける、中央値
    • をターゲットリストの他端に確認し続ける.
  • ならそこでさらに半分割って右に移動…
  • このように探し続けて、目標を見つけたら帰ります!最後まで蹴れない場合-1
    • に戻ります.

    コード実装🖊️

    def search(nums, target):

  pos1 = 0					#pos1은 처음 부분
  pos2 = len(nums) //2		#pos2는 중앙부분
  pos3 = len(nums) -1		#pos3은 끝부분

  while nums[pos2] != target: #타켓을 찾을때까지 무한 루프

    if nums[pos2] > target:	#타켓이 중앙값보다 작다면 끝부분을 땡겨오고
      
      pos3 = pos2 -1
      pos2 = (pos1 + pos3)//2

    else:					# 타켓이 중앙값보다 크다면 처음부분을 중앙부분으로 업데이트 
      pos1 = pos2 + 1		# 다시 중앙 포지션 지정
      pos2 = (pos1+pos3)//2

    if pos1 > pos3:			# 만약 이렇게 계속하다가 어느순간 list의 처음이 끝보다 커지는 경우가 발생하는데 이때는 못찾은 거니 -1을 반환하면 된당!
      return -1

  return pos2

    時間の複雑さから見ると。🤔


    ターゲットが
  • の場合、O(n)wherenはlen(list)です.
  • ですが、ずっとターゲットリストを半分に分けて探していたので、リストの半分の半分の...このように
  • は数学的にlog 2(n)なので、次のグラフのように早くターゲットの原理を見つけることができます!

    • の最後の部分🌈

    snail
    乞食版自動化配置jenkins環境構築