バイナリナビゲーション-サンプル)部品の検索

問題を理解する

コア)お客様が要求する製品番号がリストにある場合はyes、ない場合はno
input ex)
私が持っている
N = 5
[8,3,7,9,2]
お客さんが探しているもの
M = 3
[5,7,9]
入力条件)
整数1<=N<=10000
整数1<=M<=10000

本を解く

大量のデータ検索、バイナリ検索アルゴリズムは効率的です
1)N個のデータを並べ替える
2)お客様が検索するコンテンツがデータに存在するかどうかをバイナリ検索する.(合計M回)
この場合の時間的複雑さ
バイナリ・エクスプローラ:O(M logN)勘定科目の勘定科目は約2000万回(log 100000≒20)
N個のデータのソート:O(Nlogn)勘定科目の勘定科目として、約200万回の演算があります.
最終時間複雑度:O(M+N)logN

基本解答

お客様が探している目標が存在するかどうか.
m番バイナリ検索を実行します!

# 이진탐색 소스코드 구현(반복문)

def binary_search(array, target, start, end) :
  while start <= end :
    mid = (start+end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
      return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target :
      end = mid - 1
    # 중간점의 값보다 찾고자하는 값이 큰 경우 오른쪽 확인
    else :
      start = mid + 1
  return None


n = int(input())
data = list(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

data.sort() # 이진 탐색을 수행하기 위한 사전 정렬!!!!

# 손님이 확인 요청한 부품 번호를 하나씩 확인 
for target in targets :
  # 해당 부품이 존재하는지 확인
  result = binary_search(data, target, 0, n-1)

  if result != None : print('yes', end = ' ')
  else              : print('no', end =' ')

係数ソートの使用率を解く

すべての要素番号を含むサイズリストを作成します.
リストのインデックスに直接アクセスして、特定の番号の部品がショップに存在するかどうかを決定します.
カウントソートの複雑さはO(N)ですが、メモリの無駄になります.
次のリンクを参照

# N *(가게의 부품 갯수) 입력받기
n = int(input())
array = [0]*1000001

# 가게에 있는 전체 부품번호를 입력받아서 기록
for i in input().split() :
  array[int(i)] = 1

# M(손님이 확인 요청한 부품 갯수) 입력받기
m = int(input())
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x :
  # 해당 부품이 존재하는지 확인
  if array[i] == 1: print('yes', end=' ')
  else : print('no', end=' ')
  

集合型使用状況の解答

set()関数は、集合データ型を初期化するために使用されます.
集合資料型は,特定のデータが存在するか否かを単純にチェックする場合に有効である.
Python文法学習集合資料型
データ型別Pythonメソッドの時間的複雑さ
set資料型の含む複雑さはO(1)!!
Listの包含複雑度はO(N)であり,比較すると赫迅号である.

n = int(input())
array = set(map(int, input().split())) # 집합 자료형에 기록한다!!!!!
m = int(input())
x = list(map(int, input().split()))

# 손님이 확인 요청한 부품 번호를 하나씩 확인
for i in x :
  if i in array :
    print('yes', end=' ')
  else :
    print('no', end=' ')

3つの解釈があります

以上の3つの方法はすべて有効な解題方法です!