c - Divide and Conquer - Merge Sort を使用した重複の検出

Question

分割統治法を使用して、特定の配列内の重複を検出したいと考えています。これにマージソートを使用できますか:

1. 最初に配列を log N ステップで分割します

2. 次に、マージして並べ替えます

3. マージ中にカウンター変数を使用して重複を検出します。オン）

したがって、合計で O(N log N) ステップかかります...

このアプローチは正しいですか？

Answer 1

その必要はありません。あなたはO（n）でそれを行うことができます

元の配列 int A[N]; があります。タイプ bool=false の 2 番目の配列 bool a[N] も作成します。最初の配列を反復し、false の場合は a[A[i]]=true を設定します。そうでない場合は、重複が見つかりました。

Answer 2

マージソートを使用して、 O(nlogn) かかる配列をソートします。配列がソートされると、O(n) 時間で重複を検出できるため、合計時間は O(nlogn) になります。
たとえば、配列はarr[]あり、N要素があります。

1.Sort array using merge sort.

2. (a)variables 
   start -- initially at position 1 of array (arr has elements from 1 to N).
   count--- to count number of times a specific number occurs

   (b)method
   for(i=2;i<=N;i++)
   {
       if(arr[i]!=arr[start])
       { 
           printf("%d has occurred %d times",arr[start],count);
           count=1;
           start=i;
       }
       else count++;
   }
   printf("%d has occurred %d times",arr[start],count);

したがって、合計時間 O(nlogn) スペース O(n) です。