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

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

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

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

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

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

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

Ответы [ 34 ]

135 голосов
/ 07 октября 2009

Решение, предложенное моей девушкой, представляет собой разновидность слияния. Единственное изменение состоит в том, что на этапе объединения просто игнорируйте дублирующиеся значения. Это решение будет также O (n log n). При таком подходе сортировка / удаление дубликатов объединяются вместе. Тем не менее, я не уверен, имеет ли это какое-то значение.

46 голосов
/ 07 октября 2009

Я уже писал об этом однажды на SO, но я воспроизведу это здесь, потому что это довольно круто. Он использует хеширование, создавая что-то вроде хэша, установленного на месте. Он гарантированно будет O (1) в подмышечном пространстве (рекурсия - это хвостовой вызов), и, как правило, O (N) сложность времени. Алгоритм выглядит следующим образом:

  1. Возьмите первый элемент массива, это будет страж.
  2. Переупорядочьте остальную часть массива, насколько это возможно, так, чтобы каждый элемент находился в позиции, соответствующей его хешу. По завершении этого шага будут обнаружены дубликаты. Установите их равными часовому.
  3. Переместить все элементы, для которых индекс равен хешу, в начало массива.
  4. Переместить все элементы, равные часовому, кроме первого элемента массива, в конец массива.
  5. То, что осталось между правильно хешированными элементами и дублирующимися элементами, будет теми элементами, которые не могли быть помещены в индекс, соответствующий их хешу из-за столкновения. Рекурс для работы с этими элементами.

Можно показать, что это O (N), если в хешировании нет патологического сценария: даже если дубликатов нет, примерно 2/3 элементов будут исключаться при каждой рекурсии. Каждый уровень рекурсии равен O (n), где small n - количество оставшихся элементов. Единственная проблема состоит в том, что на практике это медленнее, чем быстрая сортировка, когда имеется несколько дубликатов, то есть много коллизий. Однако, когда есть огромное количество дубликатов, это удивительно быстро.

Редактировать: в текущих реализациях D hash_t составляет 32 бита. Все, что касается этого алгоритма, предполагает, что в 32-битном пространстве будет очень мало коллизий хешей, если они вообще есть. Однако столкновения могут часто происходить в пространстве модулей. Однако это предположение, по всей вероятности, будет справедливо для любого набора данных разумного размера. Если ключ меньше или равен 32 битам, это может быть собственный хэш, что означает, что конфликт в полном 32-битном пространстве невозможен. Если он больше, вы просто не сможете разместить их достаточно в адресном пространстве 32-битной памяти, чтобы это стало проблемой. Я предполагаю, что hash_t будет увеличен до 64 бит в 64-битных реализациях D, где наборы данных могут быть больше. Кроме того, если это когда-либо окажется проблемой, можно изменить хэш-функцию на каждом уровне рекурсии.

Вот реализация на языке программирования D:

void uniqueInPlace(T)(ref T[] dataIn) {
    uniqueInPlaceImpl(dataIn, 0);
}

void uniqueInPlaceImpl(T)(ref T[] dataIn, size_t start) {
    if(dataIn.length - start < 2)
        return;

    invariant T sentinel = dataIn[start];
    T[] data = dataIn[start + 1..$];

    static hash_t getHash(T elem) {
        static if(is(T == uint) || is(T == int)) {
            return cast(hash_t) elem;
        } else static if(__traits(compiles, elem.toHash)) {
            return elem.toHash;
        } else {
            static auto ti = typeid(typeof(elem));
            return ti.getHash(&elem);
        }
    }

    for(size_t index = 0; index < data.length;) {
        if(data[index] == sentinel) {
            index++;
            continue;
        }

        auto hash = getHash(data[index]) % data.length;
        if(index == hash) {
            index++;
            continue;
        }

        if(data[index] == data[hash]) {
            data[index] = sentinel;
            index++;
            continue;
        }

        if(data[hash] == sentinel) {
            swap(data[hash], data[index]);
            index++;
            continue;
        }

        auto hashHash = getHash(data[hash]) % data.length;
        if(hashHash != hash) {
            swap(data[index], data[hash]);
            if(hash < index)
                index++;
        } else {
            index++;
        }
    }


    size_t swapPos = 0;
    foreach(i; 0..data.length) {
        if(data[i] != sentinel && i == getHash(data[i]) % data.length) {
            swap(data[i], data[swapPos++]);
        }
    }

    size_t sentinelPos = data.length;
    for(size_t i = swapPos; i < sentinelPos;) {
        if(data[i] == sentinel) {
            swap(data[i], data[--sentinelPos]);
        } else {
            i++;
        }
    }

    dataIn = dataIn[0..sentinelPos + start + 1];
    uniqueInPlaceImpl(dataIn, start + swapPos + 1);
}
20 голосов
/ 07 октября 2009

Еще одна эффективная реализация

int i, j;

/* new length of modified array */
int NewLength = 1;

for(i=1; i< Length; i++){

   for(j=0; j< NewLength ; j++)
   {

      if(array[i] == array[j])
      break;
   }

   /* if none of the values in index[0..j] of array is not same as array[i],
      then copy the current value to corresponding new position in array */

  if (j==NewLength )
      array[NewLength++] = array[i];
}

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

Вывод этого кода - массив [] с размером NewLength

Здесь мы начинаем со второго элемента массива и сравниваем его со всеми элементами массива до этого массива. Мы держим дополнительную индексную переменную NewLength для изменения входного массива. Переменная NewLength инициализируется до 0.

Элемент в массиве [1] будет сравниваться с массивом [0]. Если они отличаются, то значение в массиве [NewLength] будет изменено с помощью массива [1] и увеличено на NewLength. Если они одинаковые, NewLength не будет изменен.

Итак, если у нас есть массив [1 2 1 3 1], то

В первом проходе цикла 'j' массив [1] (2) будет сравниваться с массивом 0, затем 2 будет записан в массив [NewLength] = массив [1] поэтому массив будет [1 2], так как NewLength = 2

Во втором проходе цикла 'j' массив [2] (1) будет сравниваться с массивами 0 и массивом 1. Здесь, так как array [2] (1) и array0 - это один и тот же цикл. поэтому массив будет [1 2], так как NewLength = 2

и т. Д.

19 голосов
/ 07 октября 2009

Если вы ищете старшую O-нотацию, тогда сортировка массива с помощью O (n log n) сортировки, тогда прохождение O (n) может быть лучшим маршрутом. Без сортировки вы смотрите на O (n ^ 2).

Редактировать: если вы просто делаете целые числа, то вы также можете выполнить радикальную сортировку, чтобы получить O (n).

19 голосов
/ 07 октября 2009

Как насчет:

void rmdup(int *array, int length)
{
    int *current , *end = array + length - 1;

    for ( current = array + 1; array < end; array++, current = array + 1 )
    {
        while ( current <= end )
        {
            if ( *current == *array )
            {
                *current = *end--;
            }
            else
            {
                current++;
            }
        }
    }
}

Должно быть O (n ^ 2) или меньше.

10 голосов
/ 09 октября 2009

1. Использование O (1) дополнительного пространства в O (n log n) время

Это возможно, например:

  • сначала выполните сортировку по месту O (n log n)
  • затем пройтись по списку один раз, записав первый экземпляр каждого обратно в начало списка

Я полагаю, что партнер ejel прав, что лучшим способом сделать это была бы сортировка на месте с упрощенным шагом слияния, и это, вероятно, является целью вопроса, если вы, например, так. написать новую библиотечную функцию, чтобы сделать это настолько эффективно, насколько это возможно, без возможности улучшения входных данных, и в некоторых случаях было бы полезно сделать это без хеш-таблицы, в зависимости от видов входных данных. Но я на самом деле не проверял это.

2. Использование O (много) дополнительного пространства в O (n) времени

  • объявляет массив с нулем, достаточно большой, чтобы вместить все целые числа
  • пройти массив один раз
  • установить соответствующий элемент массива равным 1 для каждого целого числа.
  • Если это уже было 1, пропустите это целое число.

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

  • возможно дешево обнулить память, или размер вставок невелик по сравнению с их количеством
  • вы с радостью попросите у вашей ОС 256 ^ sizepof (int) памяти
  • и он действительно очень эффективно кеширует его, если он гигантский

Это плохой ответ, но если у вас есть много входных элементов, но они все 8-битные целые (или, может быть, даже 16-битные целые), это может быть лучшим способом.

3. O (маленький) - лишний пробел, O (n) - желаемый раз

Как # 2, но использовать хеш-таблицу.

4. Ясный путь

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

Например. Пройдите по массиву для каждого уникального элемента (т.е. первого элемента, второго элемента (дубликаты первого были удалены) и т. Д.), Удалив все идентичные элементы. O (1) дополнительный пробел, O (n ^ 2) время.

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

7 голосов
/ 07 октября 2009

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

Это ужасно неэффективно, и вы можете ускорить его с помощью вспомогательного массива для вывода или сортировки / двоичных деревьев, но это, похоже, недопустимо.

6 голосов
/ 07 октября 2009

Если вам разрешено использовать C ++, ответ на звонок будет std::sort, а затем вызов std::unique. Сложность по времени составляет O (N log N) для сортировки и O (N) для уникального обхода.

И если C ++ не стоит на столе, нет ничего, что мешало бы написанию этих же алгоритмов на C.

6 голосов
/ 07 октября 2009

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

В Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}
5 голосов
/ 20 ноября 2012

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

Каждая итерация внешнего цикла обрабатывает один элемент массива. Если он уникален, он остается в начале массива, а если он является дубликатом, он перезаписывается последним необработанным элементом в массиве. Это решение выполняется за O (n ^ 2) времени.

#include <stdio.h>
#include <stdlib.h>

size_t rmdup(int *arr, size_t len)
{
  size_t prev = 0;
  size_t curr = 1;
  size_t last = len - 1;
  while (curr <= last) {
    for (prev = 0; prev < curr && arr[curr] != arr[prev]; ++prev);
    if (prev == curr) {
      ++curr;
    } else {
      arr[curr] = arr[last];
      --last;
    }
  }
  return curr;
}

void print_array(int *arr, size_t len)
{
  printf("{");
  size_t curr = 0;
  for (curr = 0; curr < len; ++curr) {
    if (curr > 0) printf(", ");
    printf("%d", arr[curr]);
  }
  printf("}");
}

int main()
{
  int arr[] = {4, 8, 4, 1, 1, 2, 9};
  printf("Before: ");
  size_t len = sizeof (arr) / sizeof (arr[0]);
  print_array(arr, len);
  len = rmdup(arr, len);
  printf("\nAfter: ");
  print_array(arr, len);
  printf("\n");
  return 0;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...