math - 数字对齐算法

Question

是否有一种算法可以采用两列数字并确定它们是否具有共同值？

两列：

每个值增加 0.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  

---

¹其中 sorted 表示相对于总订单。