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

Question

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

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

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

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

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

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

Answer 1

Вот версия 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;       
    }

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

Посмотрим:

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

Answer 5

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

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

Answer 6

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

Answer 7

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

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

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

Answer 8

Это наивное (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;
}

Answer 9

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

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

t=[]

output = filter(check_dump, input)

print(output)
True

Answer 10

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