アレイデュープスキャナとアルゴリズム

Question

の実行時には、私はそれには2つのタスクを得ました私が得るより多くのポイント）。

2.）アルゴリズムの実行時間を分析します。

import java.util.Arrays; 

public class Dupescanner 
{ 
    public static void main(String[] args) 
    { 
     int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8}; 
     Arrays.sort(A); 
     System.out.println("Following numbers are duplicates:"); 
     for (int n = 1; n < A.length; n++) 
     { 
      if (A[n] == A[n - 1]) 
      { 
       System.out.println(A[n]); 
      } 
     } 
    } 
} 

出力：ここ

は、（。。私は、アルゴリズムの高速化/すべてで動作します動作しますので、配列をソートする必要がありました。このために私が代わりにそれを自分でコーディングのimportを使用）最初のタスクのために私のコードです：

Following numbers are duplicates: 
1 
2 
8 

アルゴリズムは問題ありませんか？私はこれよりも速いものは考えられませんでした。あるいは、私はその仕事を理解していないと分かります。ちょうど言うなら、それは十分です： true - 重複があります。偽 - ない...ランタイム分析のために

は、私は確認されませんでしたが、私はそれは同様にしてみてくださいました：

int[] A = {1, 2, 3, 4, 5, 1, 2, 8, 8}; 

は、n個のループ費のために1

コストとあればnもコストです。 結果はn^2 + 1になります。配列のソートがカウントされるかどうかはわかりませんが、除外します。

Answer 1

あなたのアルゴリズムはO(nlogn)です。ここでのボトルネックはソートです。

ループは線形時間で実行されます。

これは実際にはelement distinctness problemです。

ハッシュテーブル（HashSet）を入力して反復処理中にすべての要素を挿入して、ハッシュと余分なスペースを許可した場合にのみ、より効率的に（漸近的複雑さの点で）解くことができます。 iterating - printしてください。

int[] array = {1, 2, 3, 4, 5, 1, 2, 8, 8}; 
Set<Integer> set = new HashSet<>(); 
System.out.println("Following numbers are duplicates:"); 
for (int e : array) { 
    if (!set.add(e)) System.out.println("" + e); 
} 

This threadは、問題の下限について説明しています。