亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

找到滿足特定屬性的元素對

找到滿足特定屬性的元素對

開滿天機 2023-08-15 16:35:18
如果給定輸入 [s1, ..., sn],并且還給定屬性 P,則程序應輸出滿足該 P 的連續對。例如,如果 P 是該對中兩個元素的總和應小于 20,則輸入[1,10,29,17]應輸出,[(1,10)]因為它是滿足此 P 的唯一連續對。為了簡單起見,我們假設檢查屬性 P 是常數時間。一個簡單的解決方案是循環遍歷列表,使其復雜度為 O(n)。例如在Python中def f(ls, P: callable):    r = []    for i in range(len(ls)-1):        if P(ls[i], ls[i+1]):            r.append((ls[i], ls[i+1]))    return rassert f([1,10,29,17], lambda x, y: x+y<=20) == [(1,10)]assert f([1,10,29,17], lambda x, y: x < y) == [(1,10),(10,29)] # checking if first is smaller than the second 但我想知道是否有一些方法可以加快這個過程。謝謝你!
查看完整描述

1 回答

?
陪伴而非守候

TA貢獻1757條經驗 獲得超8個贊

不是,沒有。由于您已將序列和屬性保留為抽象實體,因此我們沒有可以利用的固有信息來避免基本要求:我們必須檢查列表中的每個元素。這使得O(N)成為理論最小值。



查看完整回答
反對 回復 2023-08-15
  • 1 回答
  • 0 關注
  • 140 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號