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

Question

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

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

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

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

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

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

Answer 1

После рассмотрения проблемы, вот мой способ Delphi, который может помочь

var
A: Array of Integer;
I,J,C,K, P: Integer;
begin
C:=10;
SetLength(A,10);
A[0]:=1; A[1]:=4; A[2]:=2; A[3]:=6; A[4]:=3; A[5]:=4;
A[6]:=3; A[7]:=4; A[8]:=2; A[9]:=5;

for I := 0 to C-1 do
begin
  for J := I+1 to C-1 do
    if A[I]=A[J] then
    begin
      for K := C-1 Downto J do
        if A[J]<>A[k] then
        begin
          P:=A[K];
          A[K]:=0;
          A[J]:=P;
          C:=K;
          break;
        end
        else
        begin
          A[K]:=0;
          C:=K;
        end;
    end;
end;

//tructate array
setlength(A,C);
end;

Answer 2

Просто возьмите переменную x=arr[0] и выполните операцию xor, пройдя остальные элементы. Если элемент повторился, то х станет нулевым.

Таким образом, мы знаем, что элемент повторялся ранее. Это также просто займет o(n) для сканирования всех элементов в исходном массиве.

Answer 3

Во-первых, вы должны создать массив check[n], где n - это количество элементов массива, которое вы хотите сделать без дубликатов, и установить значение каждого элемента (проверочного массива) равным 1. Использование for переберите в цикле массив с дубликатами, скажите, что его имя arr, и в цикле for запишите:

{
    if (check[arr[i]] != 1) {
        arr[i] = 0;
    }
    else {
        check[arr[i]] = 0;
    }
}

При этом вы устанавливаете каждый дубликат равным нулю. Таким образом, остается только пройти через массив arr и вывести все, что не равно нулю. Заказ остается, и он занимает линейное время (3 * n).

Answer 4

Для тех, кто хочет иметь простое решение на C ++:

int* rmdup(int path[], int start, int end, int& newEnd) {
    int ret[100];
newEnd = end;
int j = start;

for (int i = start; i < end; i++) {
    if (path[i] == path[i+1]) {
    newEnd--;
        continue;
    }
    ret[j++] = path[i];
}

ret[j++] = path[end];

for(int i = start; i <= newEnd; i++)
     path[i] = ret[i];
}

Answer 5

Было бы здорово, если бы у вас была хорошая DataStructure, которая могла бы быстро определить, содержит ли она целое число. Возможно, какое-то дерево.

DataStructure elementsSeen = new DataStructure();
int elementsRemoved = 0;
for(int i=0;i<array.Length;i++){
  if(elementsSeen.Contains(array[i])
    elementsRemoved++;
  else
    array[i-elementsRemoved] = array[i];
}
array.Length = array.Length - elementsRemoved;

Answer 6

Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10}; 

Set set = new HashSet();
for(Integer i:arrayInteger)
set.add(i);

System.out.println(set);

Answer 7

В JAVA,

    Integer[] arrayInteger = {1,2,3,4,3,2,4,6,7,8,9,9,10};

    String value ="";

    for(Integer i:arrayInteger)
    {
        if(!value.contains(Integer.toString(i))){
            value +=Integer.toString(i)+",";
        }

    }

    String[] arraySplitToString = value.split(",");
    Integer[] arrayIntResult = new Integer[arraySplitToString.length];
    for(int i = 0 ; i < arraySplitToString.length ; i++){
        arrayIntResult[i] = Integer.parseInt(arraySplitToString[i]);
    }

Выход: {1, 2, 3, 4, 6, 7, 8, 9, 10}

надеюсь, что это поможет

Answer 8

Создайте BinarySearchTree со сложностью O (n).

Answer 9

Некоторые ответы, которые написаны здесь, довольно тривиальны (O (n ^ 2) или сортировка и обход в O (NlogN)), и я предполагаю, что это не то, что ожидалось в интервью для Microsoft. Очевидно, что любой ответ выше O (n) не был тем, что они искали. В обновлении говорится, что не должно быть никаких вспомогательных структур данных, поэтому любой ответ с таким (хеш-таблица, дерево, битовый массив или что-то еще) не должен быть допустимым решением.

Если вы можете выделить дополнительную память, то ответ Джеффа Б, вероятно, самый простой способ сделать это. У меня есть хороший ответ на подобные вопросы, но MAXINT должен быть ограничен размером массива. (Пример: массив размером 100 может содержать любое число от 1 до 100. Удалите дубли как исходный вопрос)

Ответ на это в O (n) времени и O (1) памяти:

// FLAG ALL DUPS IN THE ORIGIN ARRAY
int maxNumInArray = findMaxNumInArray(arr);
int dup = findMinNumInArray(arr) - 1;
for (int i=0; i < arrLength; ++i) {
    int seekIndex = arr[i] % (maxNumInArray+1);
    if (arr[seekIndex] > maxNumInArray)
        arr[i] = dup; // invalidate index
    else
        arr[seekIndex] = arr[seekIndex] + maxNumInArray;
}

// REMOVE EMPTY SPACES
int i = 0;
int j = arrLength(arr)-1;
while (i<j) {
    while (arr[i] != dup)
        ++i;
    while (arr[j] == dup)
        --j;
    swap(arr[i], arr[j]);
}

Если вы не знаете границ, мой ответ бесполезен, но вы можете попробовать поиграть с ним. Да, и этот конкретный вариант не будет работать с отрицательными числами, но это не проблема, чтобы исправить это.

Answer 10

Используйте фильтр Блума для перемешивания. Это значительно сократит накладные расходы памяти.