如果給定輸入 [s1, ..., sn],并且還給定屬性 P,則程序應(yīng)輸出滿足該 P 的連續(xù)對。例如,如果 P 是該對中兩個元素的總和應(yīng)小于 20,則輸入[1,10,29,17]應(yīng)輸出,[(1,10)]因為它是滿足此 P 的唯一連續(xù)對。為了簡單起見,我們假設(shè)檢查屬性 P 是常數(shù)時間。一個簡單的解決方案是循環(huán)遍歷列表,使其復(fù)雜度為 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貢獻(xiàn)1757條經(jīng)驗 獲得超8個贊
不是,沒有。由于您已將序列和屬性保留為抽象實體,因此我們沒有可以利用的固有信息來避免基本要求:我們必須檢查列表中的每個元素。這使得O(N)成為理論最小值。
添加回答
舉報
0/150
提交
取消