#26816: [Python]二分搜尋不會TLE呀?


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 :
2022-09-03 11:13:16
d732. 二分搜尋法 | From: [1.172.246.13] | 發表日期 : 2021-08-26 12:13

Python有個套件叫做bisect,可以參考官方文件的範例做改寫,很快就可以寫出答案了,https://docs.python.org/zh-tw/3/library/bisect.html

解起來0.4s

 

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

 

________________________________

另一個做法如同上一個解題報告,使用dict,寫起來很簡潔,四行,大概0.2s

 

input()  #  第一行的變數、長度資訊用不到

table = {v:k for k,v in enumerate(input().split(), 1)}  # v,k  鍵、值有互相調換

for k in input().split():

  print(table.get(k, 0))  # 直接使用get可以判斷有沒有鍵值,而不用擔心KeyError,並且會回傳預設值0

 

 

 

 
#26817: Re:[Python]二分搜尋不會TLE呀?


406490150@gms.tku.edu.tw (我是朱朱)

學校 : 國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 :
2022-09-03 11:13:16
d732. 二分搜尋法 | From: [1.172.246.13] | 發表日期 : 2021-08-26 12:19

另外一種建表的方式,可以用itertool.count()

 

table = dict(zip(input().split(), count(1)))

 

利用dict可以讀取[鍵值對(key-value pair)],zip()則可以產生[鍵值對],使用count()就可以把index的資訊放在value,而不會像enumerate()是放在key的位置,達成k、v互換。

 
ZeroJudge Forum