java - O(logn) 時間で ArrayList の重複要素を削除する方法

Question

arraylist の要素として文字列があり、Java を使用して O(logn) 時間でそれらを削除したい

私はHashSetコピーしてクリアし、別の配列リストにコピーして戻すために使用しようとしましたが、それは O(n) 時間だと思います。

Answer 1

配列をソートしたとしても、それは可能だとは思いませんO(n)。各要素を少なくとも 1 回チェックすることは避けられないと思うので、複雑さをO(n).

Answer 2

配列内の文字列がソートされている場合、バイナリ検索を使用して O(log n) 時間でアクセスできます。ただし、並べ替えられていない場合は、配列の各要素をチェックして、O(n) の下限を指定する必要があります。

編集: 既に作成された ArrayList から重複を削除しようとしている場合は、各要素を確認する必要があり、O(n) 時間かかります。追加を犠牲にする場合は、それらを並べ替えた順序で配列に追加できます。要素が既に存在する場合は追加しないため、重複を削除する必要はありません。ただし、追加は一定時間ではなく線形時間で実行されます。