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

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

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

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

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

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;

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

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

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

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

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

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

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

Если у вас неограниченная память, вы можете выделить битовый массив для sizeof (type-of-element-in-array) / 8 байтов, чтобы каждый бит означал, встречал ли вы уже соответствующее значение или нет.

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

У IBM есть статья ] на довольно близкую тему.

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

В Perl:

foreach $i (@myary) {
    if(!defined $seen{$i}) {
        $seen{$i} = 1;
        push @newary, $i;
    }
}

Давайте посмотрим:

• Проход O (N) для поиска минимального / максимального выделения
• битового массива для найденного
• Прохода O (N) с заменой дубликатов до конца.

В Java я бы решил это так. Не знаю, как записать это в C.

   int length = array.length;
   for (int i = 0; i < length; i++) 
   {
      for (int j = i + 1; j < length; j++) 
      {
         if (array[i] == array[j]) 
         {
            int k, j;
            for (k = j + 1, l = j; k < length; k++, l++) 
            {
               if (array[k] != array[i]) 
               {
                  array[l] = array[k];
               }
               else
               {
                  l--;
               }
            }
            length = l;
         }
      }
   }

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

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];
}

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

Результатом этого кода является array [] с размером NewLength

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

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

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

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

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

и так далее

Это можно сделать за один проход с помощью алгоритма O (N log N) и без дополнительной памяти.

Перейдите от элемента a [1] к ] a [N] . На каждом этапе i все элементы слева от a [i] составляют отсортированную кучу элементов с a [0] до a [j] . Между тем, второй индекс j , изначально равный 0, отслеживает размер кучи.

Изучите a [i] и вставьте его в кучу, которая теперь занимает элементы a [0] - a [j + 1] . Если при вставке элемента встречается повторяющийся элемент a [k] , имеющий такое же значение, не вставляйте a [i] в кучу (т. Е. Отбрасывайте его); в противном случае вставьте в кучу, который теперь увеличивается на один элемент и теперь содержит от a [0] до a [j + 1] и увеличивает j .

Продолжайте таким же образом. , увеличивая i до тех пор, пока все элементы массива не будут проверены и вставлены в кучу, которая в конечном итоге займет от a [0] до a [j] . j - это индекс последнего элемента кучи, а куча содержит только уникальные значения элементов.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

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

увеличивая i до тех пор, пока все элементы массива не будут проверены и вставлены в кучу, которая в конечном итоге займет от a [0] до a [j] . j - это индекс последнего элемента кучи, а куча содержит только уникальные значения элементов.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

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

увеличивая i до тех пор, пока все элементы массива не будут проверены и вставлены в кучу, которая в конечном итоге займет от a [0] до a [j] . j - это индекс последнего элемента кучи, а куча содержит только уникальные значения элементов.

int algorithm(int[] a, int n)
{
    int   i, j;  

    for (j = 0, i = 1;  i < n;  i++)
    {
        // Insert a[i] into the heap a[0...j]
        if (heapInsert(a, j, a[i]))
            j++;
    }
    return j;
}  

bool heapInsert(a[], int n, int val)
{
    // Insert val into heap a[0...n]
    ...code omitted for brevity...
    if (duplicate element a[k] == val)
        return false;
    a[k] = val;
    return true;
}

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

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

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

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

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

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

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

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

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

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

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

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

3. O (немного) лишнего места, O (n) - времени

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

4. Ясный путь

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

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

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

Время O (n ^ 2)

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

Время O (n ^ 2)

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

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

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

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

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

Edit: В текущих реализациях 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);
}

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

Как насчет следующего?

int* temp = malloc(sizeof(int)*len);
int count = 0;
int x =0;
int y =0;
for(x=0;x<len;x++)
{
    for(y=0;y<count;y++)
    {
        if(*(temp+y)==*(array+x))
        {
            break;
        }
    }
    if(y==count)
    {
        *(temp+count) = *(array+x);
        count++;
    }
}
memcpy(array, temp, sizeof(int)*len);

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

Некоторые из написанных здесь ответов довольно тривиальны (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]);
}

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