java - 多数の数値配列の AND を取る方法は?

Question

ソートされた正の整数の配列が 200 あります (そのうちのいくつかは 100 万を超える数を持っています)。すべての配列に存在する最初の数値を見つける必要があります。何を提案しますか？

Answer 1

• すべての配列にインデックスを保持します。
• 最初の配列の最初の番号を参照として開始します。
• n 番目の配列の最初の数値が参照よりも小さい場合は、そのインデックスを増やします。
• n 番目の配列の最初の番号が参照に等しい場合は、n を増やして次の配列に進みます。
• n 番目の配列の最初の数値が基準よりも大きい場合、その数値を基準として使用し、最初からやり直します。
• n == 201 の場合、参照はすべての配列に存在します。

編集:コード例:

while n < len(data):
    item = data[n][indices[n]]
    if item < reference:
        indices[n] += 1
    elif item == reference:
        n += 1
    elif item > reference:
        reference = item
        n = 0

print reference

Answer 2

配列に対して k-way マージを実行し、最初に出現する要素を確認できますk。

別の方法は、ヒストグラムを作成し、ヒストグラムに表示される最初の要素を選択することkです。Java のヒストグラムは、Map<Element,Integer>

どちらのソリューションもO(kn)、kは配列の数であり、 は配列nの平均サイズであるため、入力のサイズは基本的に線形です。