Обнаружение дубликатов с использованием Divide и Conquer - Merge Sort

Я хочу обнаружить дубликаты в заданном массиве с использованием подхода divide и conquer. Могу ли я использовать Merge Sort для этого:Обнаружение дубликатов с использованием Divide и Conquer - Merge Sort

Первый раскол массив в журнале N шагов
Затем сортировать путем слияния
При объединении использовать переменную счетчика для обнаружения дубликатов. O (N)

Таким образом, в общей сложности потребуется O (N журнал N) шаги ...

Является ли это правильный подход?

источник

2013-06-19 sundar

Я думаю, что ваш подход правильный, если вы хотите, чтобы вы разделили и победили только для поиска дубликатов. В противном случае, как указано в ответах, используйте divide и conquer для сортировки, а затем найдите дубликаты в O (N). Итак, общее время будет O (NlogN) – abhinav

@abhinav Как это будет O (NlogN)? Давайте возьмем - вы выполняете сортировку слиянием в O (NlogN), а затем выполняете другую сортировку в O (N) .. так что общее время будет O (NlogN) + другое O (N) для итерации? – sundar

Разве это не означает O (NLogN)? – abhinav

Вы просто используете сортировку слияния для сортировки массива, который принимает 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).

источник

2013-06-19 06:55:38

Предположим, что это займет больше, чем O (NlogN) ... потому что вы сделали сортировку слияния отдельным шагом, который будет принимать O (NlogN), а затем использовать итерацию O (N). Сожалею, что я не имел в виду это. При слиянии (объединение шага в сортировке слияния) и сравнений, мы можем подсчитать количество итераций knoe? – sundar

@sundar в первую очередь O (nlogn + n) - это O (logn), поскольку nlogn доминирует n, видя, как растут обе функции. Также очистите вашу защиту большого «O'.And да, вы можете рассчитывать дубликаты при слиянии. Но это будет означать то же самое, что и при сортировке слияния, вы обнаружите дубликаты в частях исходного массива и в методе, о котором я упомянул, что вы делаете все сразу. Но это одно и то же. ура !! –

Ты выиграл !!! Спасибо .. – sundar

Вам не нужно. Вы можете сделать это в O (n)

У вас есть исходный массив int A [N]; Создайте второй массив bool a [N], тип bool = false. Итерируйте первый массив и установите [A [i]] = true, если было ложно, иначе вы нашли дубликат.

источник

2013-06-19 06:50:15

Большое спасибо ... Но я хочу знать, будет ли работать парадигма деления и покорения или нет ... – sundar

также для этого потребуется дополнительное пространство O (N). – abhinav

Если вы можете изменить один и тот же массив, это не требует дополнительного места. Вы можете сохранить флаг bool в том же массиве. –

Обнаружение дубликатов с использованием Divide и Conquer - Merge Sort

ответ

Смежные вопросы