d732: 二分搜尋法

百千.IOhttp://zerojudge.tw/ShowProblem?problemid=d732

A串用index方法搜尋最多2*len(B)次 => TLE

百千.IO當每個b都是A[-1]

• input()
• A = input().split()
• B = input().split()
• for b in B:
• if b in A:
• print(A.index(b)+1)
• else:
• print(0)

A串用index方法搜尋len(B)次 => TLE

• input()
• A = input().split()
• B = input().split()
• for b in B:
• try:
• print(A.index(b)+1)
• except:
• print(0)

AB兩遞增串掃描比對一次 => AC

• import operator
• input()
• A=[int(a) for a in input().split()]
• B=[int(b) for b in input().split()]
• B=enumerate(B) # https://docs.python.org/3/library/functions.html#enumerate
• sortedB=sorted(B, key=operator.itemgetter(1))
• sortedBplus=[]
• i=0
• for b in sortedB:
• b=list(b)
• while b[1]>A[i]:
• i+=1
• if b[1]==A[i]:
• b.append(i+1)
• else:
• b.append(0)
• sortedBplus.append(b)
• unsortedB=sorted(sortedBplus, key=operator.itemgetter(0))
• for b in unsortedB:
• print(b[2])

• 測資的len(A)和len(B)一定很大，len(A)乘len(B)就更大，一一搜尋就會TLE
• 必須降低算法的時間複雜度
• 沒用到二分搜尋法就AC，對不起零法官 :raising_hand:
• 搶到這題的Python頭香 :sunglasses: