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

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

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

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

Это может быть показано как 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);
}

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

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

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

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

Так что если у нас есть массив [1 2 1 3 1], тогда

в первом проходе цикла 'j' массив [1] (2) будет сравниваться с array0, затем 2 будет записано в array[NewLength] = массив[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).

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

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

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

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

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

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

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

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

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

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

3. O (мало)-это дополнительное пространство, O(n)-это время

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

4. Ясный путь

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

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

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

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

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

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

В Perl:

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

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

и если C++ вне таблицы нет ничего, что удерживает эти же алгоритмы от записи в C.

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

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

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

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

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

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

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

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

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

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

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

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

это можно сделать за один проход с алгоритмом o (n log N) и без дополнительного хранения.

исходим из элемента a[1] to 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;
}

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

Как насчет следующих?

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-loop напишите это:

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