面接で答えられない質問がありました。配列内の最初の一意の要素 (整数) を見つける必要があります。例えば：
3,2,1,4,4,5,6,6,7,3,2,3
次に、一意の要素は1, 5, 7であり、 の最初の一意です1。
必要なソリューション:
O(n) 時間の複雑さ。
O(1) スペースの複雑さ。
私は言ってみました：
ハッシュマップ、ビットベクターを使用しています...しかし、それらのどれもスペースの複雑さO(1)を持っていませんでした。
誰かがスペース O(1) で解決策を教えてもらえますか?
O(1) スペースを使用する場合、重複検出が O(n * log n) よりも優れていることはよく知られています。現在の問題が O(n) 時間と O(1) メモリで解決可能であるとします。最初の非繰り返し数のインデックス 'k' を 0 以外の値として取得すると、k-1 が繰り返し数であることがわかり、配列をもう 1 回スイープすることで、その重複を取得して重複検出を O( n) 運動。
ここでも厳密ではなく、k が常に 0 である場合の最悪のケースの分析に入ることができます。
http://en.wikipedia.org/wiki/Element_distinctness_problemによると: サイズ n のマルチセットで n/k 回以上発生する要素は、時間 O(n log k) で見つかる場合があります。複数回出現する要素が必要なので、ここで k = n です。
注:これは一般的なケースでは機能しません。以下の理由を参照してください。
独創的なアイデア
おそらく、O(n) 時間と O(1) 余分なスペースで解決策があるでしょう。
O(n) 時間でヒープを構築することが可能です。ヒープの構築を参照してください。
したがって、ヒープを逆方向に構築し、配列の最後の要素から始めて、その最後の位置をルートにしました。ヒープを構築するときは、重複していない最新のアイテムを追跡します。
これは、アイテムをヒープに挿入するときに、ヒープに既に存在する同一のアイテムに遭遇することを前提としています。それを証明できるかどうかはわかりません。. .
上記が当てはまると仮定すると、ヒープの構築が完了すると、どのアイテムが最初の重複していないアイテムであったかがわかります。
うまくいかない理由
ヒープを所定の位置に構築するアルゴリズムは、配列の中間点から開始し、その点を超えるすべてのノードがリーフ ノードであると想定します。次に、逆方向 (アイテム 0 に向かって) に動作し、アイテムをヒープに移動します。アルゴリズムは特定の順序で最後の n/2 項目を調べません。また、項目がヒープに移動されると順序が変わります。
その結果、私たちができる最善のことは (それでも確実にできるかどうかはわかりませんが)、重複していない最初の項目が配列の前半にある場合にのみ見つけることです。
これは無理だと思います。これは証明ではなく、推測の証拠です。私の推論は次のとおりです...
最初に、要素の値に制限はないと言いました (負、0、正のいずれでもかまいません)。次に、スペースしかO(1)ないため、一定数以上の値を格納することはできません。したがって、これは、比較のみを使用してこれを解決する必要があることを意味します。さらに、一意の値の元の順序が失われるため、配列内の値を並べ替えたり、スワップしたりすることはできません (元の順序を保存することもできません)。
すべての整数が一意である配列を考えてみましょう。
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
配列を並べ替えずに、この配列で正しい出力を返すには、1各要素を他のすべての要素と比較して一意であることを確認し、これを逆の順序で行う必要があります。要素は最後です。これには、スペースとO(n^2)の比較が必要になりO(1)ます。
誰かが解決策を見つけたら、この回答を削除します。これをより厳密な証明にするための指針を歓迎します。