algorithm - 配列内の最小の一意の番号を見つける

Question

配列の最小一意数は次のように定義されます min{v|v occurs only once in the array} 。たとえば、{1, 4, 1, 2, 3} の最小一意数は 2 です。並べ替えよりも優れた方法はありますか?

Answer 1

これは、時間と空間の両方で O(N) ソリューションだと思います。

HashSet seenOnce;     // sufficiently large that access is O(1)
HashSet seenMultiple; // sufficiently large that access is O(1)

for each in input // O(N)
    if item in seenMultiple
        next
    if item in seenOnce
        remove item from seenOnce
        add to item seenMultiple
    else
        add to item seeOnce

smallest = SENTINEL
for each in seenOnce // worst case, O(N)
    if item < smallest
        smallest = item

整数値の範囲が限られている場合は、HashSet を値でインデックス付けされた BitArray に置き換えることができます。

Answer 2

完全な並べ替えを行う必要はありません。一方の端で明確な最小値が得られるまで、バブル ソートの内部ループを実行します。最良の場合、これには時間の複雑さが O(k * n) あります。ここで、k = 明確でない最小値の数です。ただし、最悪の場合の複雑さは O(n*n) です。したがって、これは k << n の期待値の場合に効率的です。

上記のタスクに O(n * logn) ソートアルゴリズムを適用できない限り、これは可能な限り最小限の時間の複雑さになると思います。