c - Detecting Duplicates Using Divide and Conquer - Merge Sort

Question

I want to detect duplicates in a given array using divide and conquer approach. Can I use Merge Sort for this:

1. First split the array in log N steps

2. Then sort by merging

3. While merging use a counter variable to detect duplicates. O(N)

So in total it will take O(N log N) steps...

Is this approach correct?

Answer 1

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

你有原始数组 int A[N]; 也创建一个 bool=false 类型的第二个数组 bool a[N]。迭代第一个数组并设置 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)。