2

今後のテストに向けて、コードのスニペットをいくつかレビューしています。私はこれをメモで見ましたが、リストがこのように A -> B -> C -> A の場合、方法 1 のこのコードは実際には重複を削除しないことに気付きました。別の関数 (方法 2) を書きました。実際にうまくいくと思います。皆さんはどう思いますか？方法 1 は実際には機能しませんか? 追跡が間違っていますか? ps現時点では、コンパイラは許可されていません:)

ここにコードと、それが何をすべきかの簡単な紹介があります。

方法 1: 頭と尾に 2 つの正確なものがある場合、機能しないと思います。バッファなしでソートされていないリストから重複を削除するコードを記述します。「current」は通常の反復を行い、「runner」は以前のすべてのノードを反復して重複をチェックします。複数の重複がある場合、それらはすでに削除されているため、ランナーにはノードごとに 1 つの重複しか表示されません。

public static void deleteDuplicates1(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
    LinkedListNode runner = head;
       while (runner != current) { // Check for earlier dups
          if (runner.data == current.data) {
              LinkedListNode tmp = current.next; // remove current
              previous.next = tmp;
              current = tmp; // update current to next node
              break; // all other dups have already been removed
              }
              runner = runner.next;
          }
          if (runner == current) { // current not updated - update now
               previous = current;
               current = current.next;
              }
         }
 }

私はこれがうまくいくと思っていました。方法 2:

    public void removeDuplicates2(){  
    Node current = null;  
    Node tracer = null;  

   for( current = head.next; current!=null; current=current.next){  
       for(tracer=head; tracer!=current; tracer=tracer.next){  
          if(tracer.data == current.data)  
          //DELETE THE NODE IN CURRENT  
       }  
    }  

}
4

5 に答える 5

9

最良の方法は、リンクされたリストをソートすることです。次に、隣接する要素が同じかどうかを繰り返して確認します。はいの場合、隣接する要素を削除します。これは、追加のバッファーを使用しない O(nlogn) メソッドです。

于 2011-01-02T17:59:34.670 に答える
6

「追加のバッファーなし」があなたにとって何を意味するのかはわかりませんが、私は怠け者であり、他の人は私よりもアルゴリズムを書くのがはるかに優れていると思うので、リンクされたリスト全体をHashSet して、リンクされたリストに戻します。これにより、重複を簡単に削除できます。

LinkedList result = new LinkedList(new HashSet(inputList));

または、要素の順序を維持したい場合

LinkedList result = new LinkedList(new LinkedHashSet(inputList));

これは宿題の質問であり、LinkedList を自分で実装しているように見えるので、この解決策は実行できない可能性があります ;-) しかし、いずれにせよ、O(n) ではなく O(n) の複雑さになります。 ^2) あなたの方法 1 と 2 の両方のように、どちらがすでにあなたにとってより良いかもしれません...?

于 2011-01-02T15:21:57.963 に答える
0

ロジックを修正するために上記の関数に加えられた変更しかし、関数の時間の複雑さが何であるかはわかりません。O(n^2) か O(n) か

public static Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head){ if(head == null || head.next == null) return head;

    Node prev = head;
    Node curr = head.next;
    Node temp = prev;

    while(prev.next!=null){
        if(curr != null){
            if(prev.data == curr.data){
                temp.next = curr.next;
                curr = curr.next;
            }else {
                temp = curr;
                curr = curr.next;
            }
        }else{
            prev = prev.next;
            curr = prev.next;
            temp = prev;
        }
    }
    return head;
}
于 2014-08-11T18:37:28.143 に答える