使用分而治之 - 合并排序检测重复项

Question

我想使用分而治之的方法来检测给定数组中的重复项。我可以为此使用合并排序吗：

1. 首先以 log N 步分割数组

2. 然后通过合并排序

3. 合并时使用计数器变量来检测重复项。 O(N)

所以总共需要 O(N log N) 步骤...

这种做法正确吗？

Answer 1

你不需要。你可以在 O(n) 内完成

你有原始数组int A[N]；创建第二个数组bool

seen[K]

，其中

K

是A中的最大值。将所有seen设置为false。迭代第一个数组，如果 was saw 为 false，则设置 saw[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)。