配列のユニークな要素とモバイルアプリのデータ構造は

Question

質問は

1. あなたは一度だけ発生する一つの要素を除いて二回繰り返し、すべての要素を持つ整数の配列を与えられているインタビューで尋ねた最近の下に、あなたは見つける必要がありますO（nlogn）時間の複雑さを伴うユニークな要素。配列が{2,47,2,36,3,47,36}であれば、出力はここでは3になるはずです。次の要素をチェックすることができた後、マージソートを実行できると言いましたが、彼はO（nlogn）+ O（n）を取ると言いました。また、ハッシュマップを使用して要素の数を保持できると言いましたが、結果を得るためにハッシュマップを繰り返し処理しなければならないので、もう一度noと答えました。いくつかの研究の後、私はxor演算を使用するとO（n）で出力が得られることを知りました。 O（nlogn）時間で答えを出すことができるソート以外の解決策はありますか？
2. スマートフォンを使用しているため、一度に多数のアプリを開くことができます。現在開いているアプリがすべて表示されているかどうかを確認すると、最近開いたアプリが前面に表示され、リストのどこからでもアプリを削除または閉じることができます。非常に効率的な方法でこれらのタスクをすべて実行できるjavaで利用できるコレクションがあります。私はLinkedListまたはLinkedHashMapを使うことができると言いましたが、彼は確信していませんでした。使用するには最高のコレクションは何でしょうか？インタビュアーがビッグO記法を使用してO(n log n)ソリューションを期待場合

Answer 1

1. まず、あなたの答えは何も問題はありません。我々はそれがO(x + y) = O(max(x, y))を知っています。したがって、あなたのアルゴリズムはO(n log n + n)ですが、O(n log n)と呼んでも問題ありません。しかし、ソートされた配列に一度現れる要素が、バイナリ検索を使用してO(log n)で実現できることがわかります。ヒントとして、検索を実行しながら奇数および偶数のインデックスを利用する。また、インタビュアーがO(n log n)解決策を予想した場合、トラバースの反対は不合理です。ハッシュマップソリューションは既にO(n)です。これに問題がある場合は、余分なスペースが必要です。この理由から、あなたが言及したようにXORを使うのが最善の方法です。さらに多くのソリューションがありますが、XORソリューションよりも優れています。O(n)
2. 私には、LinkedListもこのタスクに使用するのが適切です。どの場所からも削除したいし、スタック操作（push、pop、peek）を使いたいと思っています。カスタムスタックはLinkedListから構築できます。