0

最初は、時間計算量が 0(n^2) の Nested ループを使用しました。より効率的な 0(n) の解決策として、以下のコードを書きました。いずれかの要素とその .Next() が同じ値を保持しているかどうかを確認する方法について、ヘルプ/洞察を得たいと思います。それらを出します。

public class FindDuplicates {
    public static void main(String arg[]){
        int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
        List<Integer> list = new LinkedList<Integer>();

        for(int x : str) {   
            list.add(x);    
        }

        Collections.sort(list);
        System.out.println(list);

        Iterator<Integer> it = list.listIterator();  
        while(it.hasNext() && it.next() != null) { 
            /*   Pseudocode =>   if(it.next().equals(it.next.next)); */
            /* OR Pseudocode =>  if(it.next() == it.next().next) */ 
            System.out.println(it) ;
        }
    }
}
4

5 に答える 5

5

以前の値を変数に保持する必要があります。次のようになります。

 Iterator<Integer> it = list.listIterator(); 
 if (it.hasNext()) {
   Integer previous = it.next();
   while(it.hasNext()) { 
     Integer current = it.next();
     if (previous.equals(current)) {
       System.out.println("Dupe: " + current);
     }
     previous = current;
   }
 }

ここではリンクされたリストは実際には必要ないことに注意してください (他の人がすでに指摘しているように)。その場で並べ替えてから、単一のループで配列をスキャンできます。

int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
Arrays.sort(str);
for (int i = 1; i < str.length; i++) {
  if (str[i] == str[i - 1]) {
    System.out.println("Dupe: " + str[i];
  }
}

str を変更したくない場合は、HashSet の要素を追跡してください。

int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};
HashSet<Integer> seen = new HashSet<Integer>();
for (int i: str) {
  if (seen.contains(i)) {
    System.out.println("Dupe: " + i);
  } else {
    seen.add(i);
  }
}

ハッシュテーブル操作を O(1) と考えると、O(n log n) ではなく線形時間も得られます。

于 2013-11-10T20:49:18.350 に答える
2

まず、O(n) の複雑さを超えるCollections.sortを使用していることに注意してください。

あなたの質問について: O(n) の複雑さでソートされたリストで重複を見つける:

遭遇した前の値に設定する変数を 1 つだけ持つことができます。ループ内で、現在の値をその変数と比較してから、変数を現在の値に設定します。

于 2013-11-10T20:50:35.290 に答える
1

それを行うより良い方法は . 複雑さを超えるCollections.sortの代わりに、制約がない限りハッシュセットを使用します。基本的な擬似コードは次のようになります。O(N)space complexity

  if(set.contains(it)){// Check if it.info is in map or not
    System.out.println(it.info); // If it was then it is duplicate element hence print it
    }
  else{
    set.put(it);// Else if this is the first time you saw this element put it in set.
    }

このコードにはO(N)時間の複雑さがあります。

于 2013-11-10T21:04:43.943 に答える
0

配列付き、リスト付き、連結リスト付きのすべてのフォーム。

import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static void withArray() {
        int[] str = { 1, 2, 3, 4, 5, 3, 5, 4, 3, 43, 1, 33, 4, 5 };
        Arrays.sort(str);

        int previous = str[0];
        for (int i = 1; i < str.length; ++i) {
            if (str[i] == previous) {
                System.out.println("Duplicate " + previous + " and " + str[i]);
            }
            previous = str[i];
        }
        System.out.println();
    }

    public static void withList() {
        List<Integer> str = Arrays.asList(1, 2, 3, 4, 5, 3, 5, 4, 3, 43, 1, 33,
                4, 5);
        Collections.sort(str);

        int previous = str.get(0);
        for (int i = 1; i < str.size(); ++i) {
            if (str.get(i) == previous) {
                System.out.println("Duplicate " + previous + " and "
                        + str.get(i));
            }
            previous = str.get(i);
        }
        System.out.println();
    }

    public static void withLinkedList() {
        LinkedList<Integer> str = new LinkedList<Integer>(Arrays.asList(1, 2,
                3, 4, 5, 3, 5, 4, 3, 43, 1, 33, 4, 5));
        Collections.sort(str);

        Iterator<Integer> it = str.iterator();

        int previous = it.next();
        int cur;
        while (it.hasNext()) {
            cur = it.next();
            if (cur == previous) {
                System.out.println("Duplicate " + previous + " and " + cur);
            }
            previous = cur;
        }
        System.out.println();
    }

    public static void main(String arg[]) {
        withArray();
        withList();
        withLinkedList();

    }
}
于 2013-11-10T21:12:55.173 に答える
0 
int[] str={1 , 2 , 3 ,4  ,5 ,3 ,5 , 4,3,43,1,33,4,5};

LinkedList重複を見つけるためにソートするためだけに使用する必要はありません。を使用Arrays.sort(int[])して配列を並べ替えてからスキャンします。次のプログラムは、重複する整数と重複数を出力します。

int a[] = {1, 1, 1, 5, 5, 4, 4, 3, 3};

        Arrays.sort(a);

        for(int i=1 ; i<a.length;)
        {
            if(a[i] == a[i-1])
            {
                int j = i;
                for(; j<a.length; j++)
                    if(a[j]!=a[i])break;

                if(j > i)
                    System.out.println("Found duplicate: "+a[i]+" counted: "+(j - i+1));

                i = j;
            }
            else i++;

        }

出力例:

Found duplicate: 1 counted: 3
Found duplicate: 3 counted: 2
Found duplicate: 4 counted: 2
Found duplicate: 5 counted: 2
于 2013-11-10T20:50:30.657 に答える