Алгоритм: эффективный способ удаления дублирующихся целых чисел из массива

Question

Я получил эту проблему из интервью с Microsoft.

Учитывая массив случайных целых чисел, написать алгоритм на C, который удаляет дублирующиеся номера и вернуть уникальные номера в оригинале массив.

Eg Вход: {4, 8, 4, 1, 1, 2, 9} Выход: {4, 8, 1, 2, 9, ?, ?}

Одно предостережение: ожидаемый алгоритм не должен требовать сортировки массива первым. И когда элемент был удален, следующие элементы также должны быть сдвинуты вперед. В любом случае, значение элементов в конце массива, в котором элементы были сдвинуты вперед, ничтожно мало.

Обновление: Результат должен быть возвращен в исходном массиве, и вспомогательная структура данных (например, хеш-таблица) не должна использоваться. Тем не менее, я думаю, что сохранение порядка не является необходимым.

Обновление 2: Для тех, кто задается вопросом, почему эти непрактичные ограничения, это был вопрос для интервью, и все эти ограничения обсуждаются в процессе мышления, чтобы увидеть, как я могу придумать разные идеи.

Answer 1

Учитывая массив из n элементов, напишите алгоритм удаления всех дубликатов из массива за время O (nlogn)

Algorithm delete_duplicates (a[1....n])
//Remove duplicates from the given array 
//input parameters :a[1:n], an array of n elements.

{

temp[1:n]; //an array of n elements. 

temp[i]=a[i];for i=1 to n

 temp[i].value=a[i]

temp[i].key=i

 //based on 'value' sort the array temp.

//based on 'value' delete duplicate elements from temp.

//based on 'key' sort the array temp.//construct an array p using temp.

 p[i]=temp[i]value

  return p.

В других элементах поддерживается в выходном массиве с помощью «ключа». Предположим, ключ имеет длину O (n), время, необходимое для выполнения сортировки ключа, и значение равно O (nlogn). Таким образом, время, необходимое для удаления всех дубликатов из массива, составляет O (nlogn).

Answer 2

Это можно сделать за один проход, за O (N) время в количестве целых чисел на входе список и O (N) хранения в количестве уникальных целых чисел.

Пройдите по списку спереди назад, с двумя указателями "dst" и "src" инициализирован для первого элемента. Начните с пустой хеш-таблицы из "целых чисел". Если целое число в src отсутствует в хэше, запишите это в слот в dst и увеличьте dst. Добавьте целое число в src в хеш, затем увеличиваем src. Повторяйте, пока src не пройдет конец список ввода.

Answer 3

это то, что у меня есть, хотя оно не соответствует порядку, который мы можем отсортировать по возрастанию или убыванию, чтобы исправить это.

#include <stdio.h>
int main(void){
int x,n,myvar=0;
printf("Enter a number: \t");
scanf("%d",&n);
int arr[n],changedarr[n];

for(x=0;x<n;x++){
    printf("Enter a number for array[%d]: ",x);
    scanf("%d",&arr[x]);
}
printf("\nOriginal Number in an array\n");
for(x=0;x<n;x++){
    printf("%d\t",arr[x]);
}

int i=0,j=0;
// printf("i\tj\tarr\tchanged\n");

for (int i = 0; i < n; i++)
{
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    for (int j = 0; j <n; j++)
    {   
        if (i==j)
        {
            continue;

        }
        else if(arr[i]==arr[j]){
            changedarr[j]=0;

        }
        else{
            changedarr[i]=arr[i];

        }
    // printf("%d\t%d\t%d\t%d\n",i,j,arr[i],changedarr[i] );
    }
    myvar+=1;
}
// printf("\n\nmyvar=%d\n",myvar);
int count=0;
printf("\nThe unique items:\n");
for (int i = 0; i < myvar; i++)
{
        if(changedarr[i]!=0){
            count+=1;
            printf("%d\t",changedarr[i]);   
        }
}
    printf("\n");
}

Answer 4

Вставьте все элементы в binary tree the disregards duplicates - O(nlog(n)). Затем извлеките их все обратно в массив, выполнив обход - O(n). Я предполагаю, что вам не нужно сохранять порядок.