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

У меня возникла эта проблема из интервью с Microsoft.

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

Например, вход: {4, 8, 4, 1, 1, 2, 9} Выход:{4, 8, 1, 2, 9, ?, ?}

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

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

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

Как насчет:

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) или меньше.

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

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

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

Можно показать, что это O (N), при условии отсутствия патологического сценария в хешировании: даже если нет дубликатов, примерно 2/3 элементов будут удаляться при каждой рекурсии. Каждый уровень рекурсии - O (n), где маленький 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);
}

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

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], то

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

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

и так далее

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

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

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) раз.

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

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

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

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

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

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

В Perl:

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

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

Каждая итерация внешнего цикла обрабатывает один элемент массива. Если он уникален, он остается перед массивом, а если это дубликат, он перезаписывается последним необработанным элементом в массиве. Это решение выполняется за время 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;
}

Вот версия Java.

int[] removeDuplicate(int[] input){

        int arrayLen = input.length;
        for(int i=0;i<arrayLen;i++){
            for(int j = i+1; j< arrayLen ; j++){
                if(((input[i]^input[j]) == 0)){
                    input[j] = 0;
                }
                if((input[j]==0) && j<arrayLen-1){
                        input[j] = input[j+1];
                        input[j+1] = 0;
                    }               
            }
        }       
        return input;       
    }

Вот мое решение.

///// find duplicates in an array and remove them

void unique(int* input, int n)
{
     merge_sort(input, 0, n) ;

     int prev = 0  ;

     for(int i = 1 ; i < n ; i++)
     {
          if(input[i] != input[prev])
               if(prev < i-1)
                   input[prev++] = input[i] ;                         
     }
}

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

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

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

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

Посмотрим:

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

Это можно сделать за один проход с помощью алгоритма 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;
}

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

В 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* 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);

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

После рассмотрения проблемы вот мой способ 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;

Следующий пример должен решить вашу проблему:

def check_dump(x):
   if not x in t:
      t.append(x)
      return True

t=[]

output = filter(check_dump, input)

print(output)
True

import java.util.ArrayList;


public class C {

    public static void main(String[] args) {

        int arr[] = {2,5,5,5,9,11,11,23,34,34,34,45,45};

        ArrayList<Integer> arr1 = new ArrayList<Integer>();

        for(int i=0;i<arr.length-1;i++){

            if(arr[i] == arr[i+1]){
                arr[i] = 99999;
            }
        }

        for(int i=0;i<arr.length;i++){
            if(arr[i] != 99999){

                arr1.add(arr[i]);
            }
        }

        System.out.println(arr1);
}
    }

Это наивное (N * (N-1) / 2) решение. Он использует постоянное дополнительное пространство и поддерживает исходный порядок. Оно похоже на решение @Byju, но без if(){}блоков. Это также позволяет избежать копирования элемента на себя.

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

int numbers[] = {4, 8, 4, 1, 1, 2, 9};
#define COUNT (sizeof numbers / sizeof numbers[0])

size_t undup_it(int array[], size_t len)
{
size_t src,dst;

  /* an array of size=1 cannot contain duplicate values */
if (len <2) return len; 
  /* an array of size>1 will cannot at least one unique value */
for (src=dst=1; src < len; src++) {
        size_t cur;
        for (cur=0; cur < dst; cur++ ) {
                if (array[cur] == array[src]) break;
                }
        if (cur != dst) continue; /* found a duplicate */

                /* array[src] must be new: add it to the list of non-duplicates */
        if (dst < src) array[dst] = array[src]; /* avoid copy-to-self */
        dst++;
        }
return dst; /* number of valid alements in new array */
}

void print_it(int array[], size_t len)
{
size_t idx;

for (idx=0; idx < len; idx++)  {
        printf("%c %d", (idx) ? ',' :'{' , array[idx] );
        }
printf("}\n" );
}

int main(void) {    
    size_t cnt = COUNT;

    printf("Before undup:" );    
    print_it(numbers, cnt);    

    cnt = undup_it(numbers,cnt);

    printf("After undup:" );    
    print_it(numbers, cnt);

    return 0;
}

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

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

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

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

В 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}

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

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

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

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

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

Учитывая массив из 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).

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

#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");
}

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

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;