Удалить дубликаты из массива, не используя Hash Table

Question

У меня есть массив, который может содержать дубликаты элементов (более двух дубликатов элемента). Интересно, можно ли найти и удалить дубликаты в массиве:

• без использования Hash Table (строгое требование)
• без использования временного вторичного массива. Нет ограничений по сложности.

P.S : Это не домашний вопрос

Был задан вопрос моему другу в техническом интервью Yahoo

Answer 1

Сортировка исходного массива.Найдите последовательных элементов, которые равны.(То есть, что std::unique делает на земле C ++).Общая сложность составляет N lg N или просто N, если входные данные уже отсортированы.

Чтобы удалить дубликаты, вы можете копировать элементы из более позднего массива поверх более ранних элементов массива также в линейное время.Просто держите указатель на новый логический конец контейнера и копируйте следующий отдельный элемент в этот новый логический конец на каждом шаге.(Опять же, точно так же, как std::unique (На самом деле, почему бы просто не загрузить реализацию std::unique и сделать именно то, что она делает?: P))

Answer 2

O (NlogN): сортировать и заменять один и тот же элемент подряд одной копией.

O (N ² ): запускать вложенный цикл для сравнения каждого элемента с оставшимися элементами в массиве., если дубликат найден, поменяйте местами дубликат с элементом в конце массива и уменьшите размер массива на 1.

Answer 3

Нет ограничений по сложности.

Так что это кусок пирога.

// A[1], A[2], A[3], ... A[i], ... A[n]

// O(n^2)
for(i=2; i<=n; i++)
{
    duplicate = false;
    for(j=1; j<i; j++)
        if(A[i] == A[j])
             {duplicate = true; break;}
    if(duplicate)
    {
        // "remove" A[i] by moving all elements from its left over it
        for(j=i; j<n; j++)
            A[j] = A[j+1];
        n--;
    }
}

Answer 4

Удаление дубликатов на месте, сохраняющее существующий порядок списка в квадратичном времени:

for (var i = 0; i < list.length; i++) {
  for (var j = i + 1; j < list.length;) {
    if (list[i] == list[j]) {
      list.splice(j, 1);
    } else {
      j++;
    }
  }
}

Хитрость заключается в том, чтобы запустить внутренний цикл на i + 1, а не увеличивать внутренний счетчик при удалении элемента.

Код JavaScript, splice(x, 1) удаляет элемент в x.

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

list.sort();

for (var i = 1; i < list.length;) {
  if (list[i] == list[i - 1]) {
    list.splice(i, 1);
  } else {
    i++;
  }
}

Что является линейным, если только вы не посчитаете сортировку, которую вы должны, поэтому она имеет порядок сортировки - в большинстве случаев n × log (n).

Answer 5

В функциональных языках вы можете комбинировать сортировку и унификацию (это реальное слово?) За один проход.Давайте возьмем стандартный алгоритм быстрой сортировки:

- Take the first element of the input (x) and the remaining elements (xs)
- Make two new lists
- left: all elements in xs smaller than or equal to x
- right: all elements in xs larger than x
- apply quick sort on the left and right lists
- return the concatenation of the left list, x, and the right list
- P.S. quick sort on an empty list is an empty list (don't forget base case!)

Если вам нужны только уникальные записи, замените

left: all elements in xs smaller than or equal to x

на

left: all elements in xs smaller than x

Это однопроходный алгоритм O (n log n).

Пример реализации на F #:

let rec qsort = function
    | [] -> []
    | x::xs -> let left,right = List.partition (fun el -> el <= x) xs
               qsort left @ [x] @ qsort right

let rec qsortu = function
    | [] -> []
    | x::xs -> let left = List.filter (fun el -> el < x) xs
               let right = List.filter (fun el -> el > x) xs
               qsortu left @ [x] @ qsortu right

И тест в интерактивном режиме:

> qsortu [42;42;42;42;42];;
val it : int list = [42]
> qsortu [5;4;4;3;3;3;2;2;2;2;1];;
val it : int list = [1; 2; 3; 4; 5]
> qsortu [3;1;4;1;5;9;2;6;5;3;5;8;9];;
val it : int list = [1; 2; 3; 4; 5; 6; 8; 9]

Answer 6

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

function removeDuplicates(arr) {
    var results = [], dups = []; 

    for (var i = 0; i < arr.length; i++) {

        // check if not a duplicate
        if (dups[arr[i]] === undefined) {

            // save for next check to indicate duplicate
            dups[arr[i]] = 1; 

            // is unique. append to output array
            results.push(arr[i]);
        }
    }

    return results;
}

Answer 7

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

Без альтернативного хранилища (т.е. O (1) хранилища, в котором вы, вероятно, будете использовать некоторые счетчики / указатели), кажется очевидным, что ожидается деструктивная операция, возможно, стоит указать на это интервьюеру .

Теперь реальный вопрос: хотите ли вы сохранить относительный порядок элементов? т.е. эта операция должна быть стабильной?

Стабильность сильно влияет на доступные алгоритмы (и, следовательно, на сложность).

Наиболее очевидный выбор - перечислить Алгоритмы сортировки , в конце концов, после сортировки данных довольно просто получить уникальные элементы.

Но если вам нужна стабильность, вы не можете на самом деле сортировать данные (поскольку вы не можете получить «правильный» порядок обратно), и поэтому мне интересно, разрешается ли это менее чем за O (N ** 2), если речь идет о стабильности.