數字對齊算法

Question

是否有一個算法，將採取兩列數字，並確定它們是否有一個共同的價值？

兩列：

每個值增加一個.3。另一個增加不規律。我想確定兩列是否有共同的價值。

.3 .1 
.6 .2 
.9 .4 
1.2 .5 
1.5 .9 
1.8 .13 

Answer 1

如果兩個串聯增加（或排序在一般），有一個O(n)溶液。你不能做得比這更好，因爲在最壞的情況下，你需要查看不斷增加的列表中的每個元素至少一次。

簡單地以拉鍊式的方式同時遍歷兩者：始終從列表中獲取下一個元素，該元素當前比另一個元素小。

> .3 .1 < | > .3 .1 | > .3 .1 | .3 .1 | .3 .1 | .3 .1 
    .6 .2 | .6 .2 < | .6 .2 | > .6 .2 | > .6 .2 | > .6 .2 
    .9 .4 | .9 .4 | .9 .4 < | .9 .4 < | .9 .4 | .9 .4 
    .12 .5 | .12 .5 | .12 .5 | .12 .5 | .12 .5 < | .12 .5 
    .15 .9 | .15 .9 | .15 .9 | .15 .9 | .15 .9 | .15 .9 < 
    .18 .13 | .18 .13 | .18 .13 | .18 .13 | .18 .13 | .18 .13 

---

凡排序裝置相對於一total order。