math - 番号整列アルゴリズム

Question

2 列の数値を取り、値が共通しているかどうかを判断するアルゴリズムはありますか?

2 つの列:

値ごとに 1 が 0.3 ずつ増加します。もう一方は不規則に増加します。2 つの列に共通の値があるかどうかを判断したいと考えています。

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

Answer 1

両方の系列が増加している(または一般に¹でソートされている) 場合、O(n)解決策があります。最悪の場合、不規則に増加するリスト内のすべての要素を少なくとも 1 回確認する必要があるため、これ以上のことはできません。

ジッパーのような方法で両方を同時にトラバースするだけです。現在、他の要素よりも小さい要素を持つ、リストから次の要素を常に取得します。

> .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  

---

^{1ソートされている場合は、}合計順序に関して意味します。