Algorytm: efektywny sposób usuwania zduplikowanych liczb całkowitych z tablicy

Rozwiązanie zaproponowane przez moją dziewczynę jest odmianą typu merge. Jedyną modyfikacją jest to, że podczas etapu scalania po prostu ignoruj zduplikowane wartości. Takie rozwiązanie byłoby również O (n log n). W tym podejściu sortowanie / usuwanie duplikacji są połączone ze sobą. Jednak nie jestem pewien, czy to robi jakąś różnicę.

Zamieściłem to już kiedyś na SO, ale powtórzę to tutaj, bo jest całkiem fajne. Używa hashowania, budując coś w rodzaju zestawu hash. Jest gwarantowana jako o (1) w przestrzeni pachowej(rekurencja jest wywołaniem ogonowym) i zazwyczaj jest złożonością czasową O (N). Algorytm jest następujący:

1. weź pierwszy element tablicy, to będzie sentinel.
2. Zmień kolejność reszty tablicy, tak bardzo, jak to możliwe, tak, że każdy element jest w pozycji odpowiadający jego hashowi. Po zakończeniu tego kroku zostaną odkryte duplikaty. Ustaw je równo sentinelowi.
3. Przenieś wszystkie elementy, dla których indeks jest równy hashowi na początek tablicy.
4. Przenieś wszystkie elementy, które są równe sentinel, z wyjątkiem pierwszego elementu tablicy, na koniec tablicy.
5. pomiędzy odpowiednio zahaszowanymi i duplikowanymi elementami pozostaną elementy, których nie można umieścić w indeksie odpowiadającym ich hash z powodu kolizji. Rekurencja, aby poradzić sobie z tymi elementami.

Można to wykazać jako O (N) pod warunkiem, że nie ma patologicznego scenariusza w hashowaniu: nawet jeśli nie ma duplikatów, około 2/3 elementów zostanie wyeliminowanych przy każdej rekurencji. Każdy poziom rekurencji to O (n), gdzie małe n to ilość pozostałych elementów. Jedyny problem polega na tym, że w praktyce jest wolniejszy niż szybki, gdy jest mało duplikatów, czyli dużo kolizji. Jednak, gdy tam są ogromne ilości duplikatów, to zadziwiająco szybko.

Edit: w obecnych implementacjach d hash_t wynosi 32 bity. Wszystko w tym algorytmie zakłada, że będzie bardzo niewiele, jeśli w ogóle, kolizji hashowych w pełnej 32-bitowej przestrzeni. Kolizje mogą jednak występować często w przestrzeni modularnej. Jednak to założenie najprawdopodobniej będzie prawdziwe dla każdego rozsądnego zbioru danych. Jeśli klucz jest mniejszy lub równy 32 bitom, może to być jego własny hash, co oznacza, że kolizja w całości 32-bitowa przestrzeń jest niemożliwa. Jeśli jest większy, po prostu nie możesz zmieścić ich wystarczająco dużo w 32-bitowej przestrzeni adresowej pamięci, aby mógł to być problem. Zakładam, że hash_t zostanie zwiększony do 64 bitów w 64-bitowych implementacjach D, gdzie zbiory danych mogą być większe. Co więcej, jeśli kiedykolwiek okaże się to problemem, można zmienić funkcję hash na każdym poziomie rekursji.

Oto implementacja w języku programowania 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);
}

Jedna bardziej efektywna implementacja

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

W tej implementacji nie ma potrzeby sortowania tablicy. Również jeśli zostanie znaleziony duplikat elementu, nie ma potrzeby przesuwania wszystkich elementów Po tym o jedną pozycję.

Wyjście tego kodu to tablica [] o rozmiarze NewLength

Tutaj zaczynamy od 2 elementu w tablicy i porównujemy go ze wszystkimi elementami w tablicy aż do tej tablicy. Posiadamy dodatkową zmienną indeksu 'NewLength' do modyfikacji tablica wejściowa. Zmienna NewLength jest inicjalizowana na 0.

Element w tablicy [1] zostanie porównany z tablicą[0]. Jeżeli są różne, wtedy wartość w tablicy [NewLength] zostanie zmodyfikowana tablicą [1] i przyrostem NewLength. Jeśli są takie same, NewLength nie będzie modyfikowany.

Więc jeśli mamy tablicę [1 2 1 3 1], then

W pierwszym przebiegu pętli 'j', tablica[1] (2) zostanie porównana z array0, następnie 2 zostanie zapisane do array[NewLength] = array[1] tak więc tablica będzie [1 2], ponieważ NewLength = 2

W drugim przebiegu pętli 'j', tablica [2] (1) zostanie porównana z tablicami array0 i array1. Tutaj ponieważ array [2] (1) i array0 są tą samą pętlą zostanie przerwana. tak więc tablica będzie [1 2] ponieważ NewLength = 2

I tak dalej

Jeśli szukasz nadrzędnej notacji O, to sortowanie tablicy za pomocą sortowania O (N log n) może być najlepszą trasą. Bez sortowania patrzysz na O (N^2).

Edit: jeśli robisz tylko liczby całkowite, możesz również zrobić sortowanie radix, aby uzyskać O (n).

1. Użycie o (1) dodatkowej przestrzeni, w czasie O (n log n)

Jest to możliwe, na przykład:

• najpierw zrób in-place O (N log n) sort
• Następnie przejdź przez Listę raz, zapisując pierwsze wystąpienie każdego z powrotem do początku listy

Uważam, że partner ejel ma rację, że najlepszym sposobem na to byłoby połączenie w miejscu z uproszczonym krokiem scalania, i że to jest prawdopodobnie intencją pytania, jeśli byłeś np. pisanie a nowa funkcja biblioteki, aby zrobić to tak efektywnie, jak to możliwe, bez możliwości poprawy danych wejściowych, i nie byłoby przypadków, byłoby przydatne zrobić to bez tabeli hash, w zależności od rodzaju danych wejściowych. Ale jeszcze tego nie sprawdziłem.

2. Użycie o (dużo) dodatkowej przestrzeni, w O (N) czasie

• declare a zero ' d array big enough to hold all integers
• przejdź przez tablicę raz
• ustaw odpowiedni element tablicy na 1 dla każdego liczba całkowita.
• jeśli było już 1, pomiń tę liczbę całkowitą.

To działa tylko wtedy, gdy istnieje kilka wątpliwych założeń:

• możliwe jest tanie zerowanie pamięci, lub rozmiar wejść jest mały w porównaniu do ich liczby
• z przyjemnością poprosisz swój system operacyjny o pamięć o rozmiarze 256^(int)
• i będzie buforować go dla Ciebie naprawdę bardzo skutecznie, jeśli jest gigantyczny

To zła odpowiedź, ale jeśli masz dużo elementów wejściowych, ale są one wszystkie 8-bitowe liczby całkowite (a może nawet 16-bitowe liczby całkowite) to może być najlepszy sposób.

3. O(mała)-dodatkowa przestrzeń, O (N)-czas

Jako # 2, ale Użyj tabeli hash.

4. The clear way

Jeśli liczba elementów jest mała, pisanie odpowiedniego algorytmu nie jest przydatne, jeśli inny kod jest szybszy do napisania i szybszy do odczytania.

Np. Przejdź przez tablicę dla każdego unikalnego elementu (tj. pierwszy element, drugi element( duplikaty pierwszego po usunięciu) itp.) usuwając wszystkie identyczne elementy. O (1) dodatkowa przestrzeń, O (N^2) Czas.

Np. Użyj funkcji bibliotecznych, które to robią. wydajność zależy od tego, który masz łatwo dostępny.

Cóż, jego podstawowa implementacja jest dość prosta. Przejrzyj wszystkie elementy, sprawdź, czy w pozostałych są duplikaty, a resztę przesuń nad nimi.

Jest to strasznie nieefektywne i można go przyspieszyć przez helper-array dla drzewa wyjściowego lub sortowania / binarnego, ale wydaje się, że nie jest to dozwolone.

Możesz to zrobić jednym ruchem, jeśli chcesz poświęcić pamięć. Możesz po prostu przeliczyć, czy widzisz liczbę całkowitą w tablicy hash/asocjacyjnej. Jeśli już widziałeś liczbę, usuń ją w trakcie pracy lub jeszcze lepiej, Przenieś liczby, których nie widziałeś, do nowej tablicy, unikając przesunięcia w oryginalnej tablicy.

W Perlu:

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

Jeśli możesz używać C++, wywołanie do std::sort, a następnie wywołanie do std::unique da ci odpowiedź. Złożoność czasowa wynosi O (N log N) dla sortowania i O (N) dla unikalnego przejścia.

I jeśli C++ jest poza tabelą, to nie ma nic, co powstrzymuje te same algorytmy przed napisaniem w C.

Wartością zwracaną funkcji powinna być liczba unikalnych elementów i wszystkie są przechowywane z przodu tablicy. Bez tych dodatkowych informacji nie będziesz nawet wiedział, czy były jakieś duplikaty.

Każda iteracja zewnętrznej pętli przetwarza jeden element tablicy. Jeśli jest unikalna, pozostaje w przedniej części tablicy, a jeśli jest duplikatem, jest nadpisywana przez ostatni nieprzetworzony element w tablicy. Rozwiązanie to działa w czasie 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;
}

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

Tablica powinna być oczywiście "przesuwana" od prawej do lewej, aby uniknąć nienaturalnego kopiowania wartości tam iz powrotem.

Jeśli masz nieograniczoną pamięć, możesz przydzielić tablicę bitów dla sizeof(type-of-element-in-array) / 8 bajtów, aby każdy bit oznaczał, czy napotkałeś już odpowiednią wartość, czy nie.

Jeśli Nie, Nie mogę wymyślić nic lepszego niż przemierzanie tablicy i porównywanie każdej wartości z wartościami, które po niej następują, a następnie jeśli zostanie znaleziony duplikat, usuń te wartości całkowicie. To jest gdzieś blisko O(n^2) (lub O((n^2-n)/2)).

IBM ma artykuł na dość bliski temat.

Zobaczmy:

• O (N) pass to find min / max allocate
• bit-tablica dla znalezionych
• O(N) pass Zamiana duplikatów na koniec.

Oto moje rozwiązanie.

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

W Javie rozwiązałbym to tak. Nie wiem jak to napisać w 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;
         }
      }
   }

Można to zrobić w jednym przejściu z algorytmem o(n log N) i bez dodatkowej pamięci.

Przechodzimy od elementu a[1] do a[N]. Na każdym etapie i wszystkie elementy po lewej stronie a[i] składają się z posortowanej sterty elementów a[0] do a[j]. W międzyczasie drugi indeks j, początkowo 0, śledzi rozmiar sterty.

Zbadaj a[i] i włóż go do sterty, która teraz zajmuje Elementy a[0] do a[j+1]. Gdy element jest wstawiany, jeśli element jest duplikowany a[k] jeśli napotkasz taką samą wartość, nie wstawiaj a[i] do sterty (tzn. odrzuć ją); w przeciwnym razie Wstaw ją do sterty, która teraz rośnie o jeden element i składa się teraz z a[0] do a[j+1] i inkrement j.

Kontynuuj w ten sposób, zwiększając i aż wszystkie elementy tablicy zostaną zbadane i wstawione do sterty, która ostatecznie zajmuje a[0] do a[j]. j jest indeksem ostatniego elementu sterty, A sterta zawiera tylko unikalny element wartości.

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

Patrząc na przykład, nie jest to dokładnie to, o co poproszono, ponieważ wynikowa tablica zachowuje pierwotny porządek elementów. Ale jeśli ten wymóg jest złagodzony, powyższy algorytm powinien załatwić sprawę.

A co powiesz na to?

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

Próbuję zadeklarować tablicę temp i umieścić w niej elementy przed skopiowaniem wszystkiego z powrotem do oryginalnej tablicy.

Po przejrzeniu problemu, oto mój sposób delphi, który może pomóc

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;

Poniższy przykład powinien rozwiązać twój problem:

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

Jest to roztwór naiwny (N*(N-1)/2). Wykorzystuje stałą dodatkową przestrzeń i zachowuje pierwotny porządek. Jest podobny do rozwiązania @Byju, ale nie używa if(){} bloków. Unika również kopiowania elementu na siebie.

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

Można to zrobić w jednym przejściu, w czasie O (N) w liczbie liczb całkowitych na wejściu lista, oraz O (N) Przechowywanie w liczbie unikalnych liczb całkowitych.

Przejdź przez Listę od przodu do tyłu, z dwoma wskaźnikami " dst " i "src" zainicjalizowane do pierwszej pozycji. Zacznij od pustej tabeli hash "liczby całkowite widziane". Jeśli liczba całkowita W src nie jest obecna w haśle, zapisz go do gniazda w dst i zwiększ dst. Dodaj liczbę całkowitą W src do hasha, a następnie zwiększ src. Powtarzaj do src mija koniec lista wejść.

Wstaw wszystkie elementy w binary tree the disregards duplicates - O(nlog(n)). Następnie wyciągnij wszystkie z powrotem do tablicy, wykonując traversal - O(n). Zakładam, że nie potrzebujesz ochrony porządku.

Użyj filtra bloom do hashowania. To znacznie zmniejszy obciążenie pamięci.

W języku 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]);
    }

Wyjście: { 1, 2, 3, 4, 6, 7, 8, 9, 10}

Mam nadzieję, że to pomoże

Create a BinarySearchTree który ma O (N) złożoność.

Najpierw należy utworzyć tablicę check[n] gdzie n jest liczbą elementów tablicy, którą chcemy utworzyć bez duplikatów i ustawić wartość każdego elementu(tablicy kontrolnej) równą 1. Używając pętli for przemierzaj tablicę z duplikatami, powiedzmy, że jej nazwa to arr, a w pętli for napisz to:

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

Z tym ustawiasz każdy duplikat równy zeru. Więc jedyne co pozostaje do zrobienia, to przemierzyć tablicę arr i wydrukować wszystko, co nie jest równe zeru. Order zostaje i zajmuje czas liniowy (3 * n).

biorąc pod uwagę tablicę N elementów, napisz algorytm usuwający wszystkie duplikaty z tablicy w czasie 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.

W pozostałych elementach jest utrzymywany w macierzy wyjściowej przy pomocy 'klucza'. Rozważ, że klucz ma długość O (n), czas potrzebny na wykonanie sortowania na kluczu, a wartość to O(nlogn). Czas potrzebny na usunięcie wszystkich duplikatów z tablicy to O (nlogn).

To jest to, co mam, choć mylą kolejność możemy sortować rosnąco lub malejąco, aby to naprawić.

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

Byłoby fajnie, gdybyś miał dobrą strukturę danych, która może szybko stwierdzić, czy zawiera liczbę całkowitą. Może jakieś drzewo.

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;