d732: 二分搜尋法
編輯歷史
| 時間 | 作者 | 版本 |
|---|---|---|
| 2017-07-19 14:10 – 14:10 | r0 – r1 | |
顯示 diff-
+ d732: 二分搜尋法
+ http://zerojudge.tw/ShowProblem?problemid=d732
+ A串用index方法搜尋最多2*len(B)次 => TLE
+ *當每個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:
|
||