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

Mam ten problem z wywiadu z Microsoftem.

Mając tablicę losowych liczb całkowitych, napisz algorytm w C, który usuwa zduplikowane liczby i zwraca unikalne liczby z oryginalnej tablicy.

Np. Wejście: {4, 8, 4, 1, 1, 2, 9} wyjście:{4, 8, 1, 2, 9, ?, ?}

Jedynym zastrzeżeniem jest to, że oczekiwany algorytm nie powinien wymagać, aby tablica była najpierw sortowana. Po usunięciu elementu należy również przesunąć do przodu następujące elementy. W każdym razie wartość elementów na końcu tablicy, w której elementy zostały przesunięte do przodu, jest pomijalna.

Aktualizacja: Wynik musi zostać zwrócony w oryginalnej tablicy i nie należy używać pomocniczej struktury danych (np. Tablicy hashy). Jednak wydaje mi się, że zachowanie porządku nie jest konieczne.

Aktualizacja2: Dla tych, którzy zastanawiają się, dlaczego te niepraktyczne ograniczenia, było to pytanie wywiadu i wszystkie te ograniczenia są omawiane podczas procesu myślenia, aby zobaczyć, jak mogę wymyślić różne pomysły.

Co powiesz na:

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

Powinien wynosić O (n ^ 2) lub mniej.

Rozwiązanie zaproponowane przez moją dziewczynę to odmiana sortowania przez scalanie. Jedyną modyfikacją jest to, że podczas etapu scalania po prostu zignoruj ​​zduplikowane wartości. To rozwiązanie również byłoby O (n log n). W tym podejściu sortowanie / usuwanie duplikatów są połączone razem. Jednak nie jestem pewien, czy to robi jakąkolwiek różnicę.

Opublikowałem to już raz w SO, ale powielę to tutaj, ponieważ jest całkiem fajne. Używa haszowania, budując coś w rodzaju ustawionego hasha. Gwarantuje to, że jest O (1) w przestrzeni pachowej (rekurencja jest wywołaniem ogonowym) i zwykle jest złożonością czasową O (N). Algorytm wygląda następująco:

1. Weź pierwszy element tablicy, to będzie wartownik.
2. Zmień kolejność reszty tablicy tak bardzo, jak to możliwe, tak aby każdy element znajdował się na pozycji odpowiadającej jego hashu. Po zakończeniu tego kroku zostaną odkryte duplikaty. Ustaw je jako wartowników.
3. Przenieś wszystkie elementy, których indeks jest równy skrótowi, na początek tablicy.
4. Przenieś wszystkie elementy, które są równe wartownikowi, z wyjątkiem pierwszego elementu tablicy, na koniec tablicy.
5. Pomiędzy odpowiednio zaszyfrowanymi elementami a zduplikowanymi elementami pozostaną elementy, których nie można było umieścić w indeksie odpowiadającym ich hashowi z powodu kolizji. Powtarzaj się, aby poradzić sobie z tymi elementami.

Można wykazać, że jest to O (N), pod warunkiem, że nie ma patologicznego scenariusza w haszowaniu: nawet jeśli nie ma duplikatów, około 2/3 elementów zostanie wyeliminowanych przy każdej rekursji. Każdy poziom rekurencji to O (n), gdzie małe n to liczba pozostałych elementów. Jedynym problemem jest to, że w praktyce jest to wolniejsze niż sortowanie szybkie, gdy jest niewiele duplikatów, czyli dużo kolizji. Jednak gdy jest dużo duplikatów, jest to zadziwiająco szybkie.

Edycja: W obecnych implementacjach D hash_t ma 32 bity. Wszystko w tym algorytmie zakłada, że ​​będzie bardzo niewiele, jeśli w ogóle, kolizji skrótów w pełnej 32-bitowej przestrzeni. Jednak zderzenia mogą występować często w przestrzeni modułów. Jednak założenie to z dużym prawdopodobieństwem będzie prawdziwe dla każdego zbioru danych o rozsądnej wielkości. Jeśli klucz jest mniejszy lub równy 32 bitom, może to być jego własny hash, co oznacza, że ​​kolizja w pełnej 32-bitowej przestrzeni jest niemożliwa. Jeśli jest większy, po prostu nie możesz zmieścić ich wystarczającej liczby w 32-bitowej przestrzeni adresowej pamięci, aby stanowiło to 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. Ponadto, jeśli kiedykolwiek okaże się to problemem, można zmienić funkcję skrótu 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);
}

Jeszcze jedna wydajniejsza realizacja

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 zduplikowany element, nie ma potrzeby przesuwania wszystkich elementów po tym o jedną pozycję.

Dane wyjściowe tego kodu to tablica [] o rozmiarze NewLength

Tutaj zaczynamy od drugiego elementu tablicy i porównujemy go ze wszystkimi elementami tablicy do tej tablicy. Posiadamy dodatkową zmienną indeksu „NewLength” do modyfikacji tablicy wejściowej. Wartość zmienna NewLength jest inicjalizowana na 0.

Element w tablicy [1] zostanie porównany z tablicą [0]. Jeśli są różne, to wartość w tablicy [NewLength] zostanie zmodyfikowana za pomocą tablicy [1] i zwiększy wartość NewLength. Jeśli są takie same, NewLength nie zostanie zmodyfikowana.

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

W pierwszym przebiegu pętli „j” tablica [1] (2) zostanie porównana z tablicą 0, a następnie 2 zostaną zapisane w tablicy [NewLength] = tablica [1], więc tablica będzie miała wartość [1 2], ponieważ NewLength = 2

W drugim przebiegu pętli 'j' tablica [2] (1) zostanie porównana z tablicą0 i tablicą1. Tutaj, ponieważ tablica [2] (1) i tablica0 są tą samą pętlą, tutaj zostanie przerwana. więc tablica będzie miała wartość [1 2], ponieważ NewLength = 2

i tak dalej

Jeśli szukasz lepszej notacji O, to sortowanie tablicy za pomocą sortowania O (n log n), a następnie wykonanie przejścia O (n) może być najlepszą drogą. Bez sortowania patrzysz na O (n ^ 2).

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

1. Wykorzystując O (1) dodatkową przestrzeń, w czasie O (n log n)

Jest to możliwe na przykład:

• Najpierw wykonaj sortowanie w miejscu O (n log n)
• następnie przejrzyj listę raz, zapisując pierwsze wystąpienie każdego z powrotem na początek listy

Uważam, że partner firmy ejel ma rację, że najlepszym sposobem na zrobienie tego byłoby sortowanie przez scalanie na miejscu z uproszczonym krokiem scalania i prawdopodobnie taki jest cel pytania, jeśli np. napisanie nowej funkcji bibliotecznej, aby robić to tak wydajnie, jak to możliwe, bez możliwości ulepszania danych wejściowych, a byłyby przypadki, gdy byłoby to przydatne bez tablicy mieszającej, w zależności od rodzaju danych wejściowych. Ale tak naprawdę tego nie sprawdziłem.

2. Wykorzystanie O (partii) dodatkowej przestrzeni w czasie O (n)

• zadeklaruj tablicę zerową wystarczająco dużą, aby pomieścić wszystkie liczby całkowite
• raz przejść przez tablicę
• ustaw odpowiedni element tablicy na 1 dla każdej liczby całkowitej.
• Jeśli była już 1, pomiń tę liczbę całkowitą.

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

• możliwe jest tanie zerowanie pamięci lub rozmiar int jest mały w porównaniu z ich liczbą
• z przyjemnością poprosisz swój system operacyjny o 256 ^ sizepof (int) pamięci
• i zapisze go w pamięci podręcznej naprawdę, naprawdę wydajnie, jeśli jest gigantyczny

To zła odpowiedź, ale jeśli masz DUŻO elementów wejściowych, ale wszystkie są 8-bitowymi liczbami całkowitymi (a może nawet 16-bitowymi liczbami całkowitymi), może to być najlepszy sposób.

3. O (mało) -ish dodatkowa przestrzeń, O (n) -ish czas

Jak # 2, ale użyj tabeli skrótów.

4. Przejrzysta droga

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

Na przykład. Przejdź przez tablicę dla każdego unikalnego elementu (tj. Pierwszy element, drugi element (duplikaty pierwszego zostały usunięte) itp.), Usuwając wszystkie identyczne elementy. O (1) dodatkowa spacja, O (n ^ 2) czas.

Na przykład. Użyj funkcji bibliotecznych, które to robią. wydajność zależy od tego, co masz łatwo dostępne.

Cóż, jego podstawowa implementacja jest dość prosta. Przejrzyj wszystkie elementy, sprawdź, czy w pozostałych nie ma duplikatów, a resztę przesuń na nie.

Jest to strasznie nieefektywne i można go przyspieszyć za pomocą tablicy pomocniczej dla danych wyjściowych lub drzew sortowania / binarnego, ale wydaje się, że nie jest to dozwolone.

Jeśli możesz używać C ++, wywołanie do, std::sortpo którym następuje połączenie do std::unique, da ci odpowiedź. Złożoność czasowa wynosi O (N log N) dla sortowania i O (N) dla unikalnego przejścia.

A jeśli C ++ jest poza tabelą, nie ma niczego, co powstrzymywałoby te same algorytmy przed zapisaniem w C.

Możesz to zrobić w jednym przejściu, jeśli chcesz poświęcić pamięć. Możesz po prostu sprawdzić, czy widziałeś liczbę całkowitą, czy nie w tablicy hash / asocjacyjnej. Jeśli widziałeś już liczbę, usuń ją na bieżąco lub, jeszcze lepiej, przenieś liczby, których nie widziałeś, do nowej tablicy, unikając wszelkich przesunięć w oryginalnej tablicy.

W Perlu:

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

Wartością zwracaną przez funkcję powinna być liczba unikalnych elementów i wszystkie są przechowywane na początku tablicy. Bez tych dodatkowych informacji nie dowiesz się nawet, czy były jakieś duplikaty.

Każda iteracja zewnętrznej pętli przetwarza jeden element tablicy. Jeśli jest unikalny, pozostaje na początku tablicy, a jeśli jest duplikatem, jest nadpisywany przez ostatni nieprzetworzony element tablicy. To rozwiązanie 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;       
    }

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

Tablica powinna oczywiście być „przechodzona” od prawej do lewej, aby uniknąć niepotrzebnego kopiowania wartości tam iz powrotem.

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

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

IBM opublikował artykuł na dość bliski temat.

Zobaczmy:

• O (N) pass, aby znaleźć alokację min / max
• tablica bitów dla znalezionych
• O (N) przechodzi zamiana duplikatów do końca.

Można to zrobić w jednym przebiegu z algorytmem O (N log N) i bez dodatkowej pamięci.

Przejdź od elementu a[1]do a[N]. Na każdym etapie iwszystkie elementy po lewej stronie a[i]tworzą posortowaną stertę elementówa[0] przez a[j]. W międzyczasie drugi indeks j, początkowo 0, śledzi rozmiar sterty.

Zbadać a[i]i włóż ją do sterty, która teraz zajmuje elementy a[0]do a[j+1]. Gdy element jest wstawiany, jeśli a[k]napotkany zostanie zduplikowany element o tej samej wartości, nie wkładaj a[i]go do sterty (tj. Odrzuć go); w przeciwnym razie włóż go do stosu, który teraz rośnie o jeden element i zawieraa[0] z a[j+1], i przyrost j.

Następnie w ten sposób zwiększając iaż wszystkie elementy tablicy zostały przebadane i umieszczony w stosie, która kończy się zajmując a[0]się a[j].jjest indeksem ostatniego elementu sterty, a sterta zawiera tylko unikatowe wartości elementów.

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 pytano, ponieważ wynikowa tablica zachowuje pierwotną kolejność elementów. Ale jeśli ten wymóg zostanie złagodzony, powyższy algorytm powinien załatwić sprawę.

W Javie rozwiązałbym to w ten sposób. 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;
         }
      }
   }

A co z następującymi?

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ę tymczasową i umieścić w niej elementy przed skopiowaniem wszystkiego z powrotem do oryginalnej tablicy.

Po przeanalizowaniu problemu, oto moja metoda delphi, która 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);
}
    }

To jest naiwne (N * (N-1) / 2) rozwiązanie. Wykorzystuje stałą dodatkową przestrzeń i zachowuje oryginalny 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 przebiegu, w czasie O (N) w liczbie liczb całkowitych na liście wejściowej i w pamięci O (N) w liczbie unikalnych liczb całkowitych.

Przejrzyj listę od początku do końca, z dwoma wskaźnikami „dst” i „src” zainicjowanymi do pierwszej pozycji. Zacznij od pustej tablicy mieszającej zawierającej „liczby całkowite widoczne”. Jeśli liczba całkowita w src nie jest obecna w haszu, zapisz ją w slocie w dst i zwiększ dst. Dodaj liczbę całkowitą w src do skrótu, a następnie zwiększ src. Powtarzaj, aż src minie koniec listy wejściowej.

Wstaw wszystkie elementy w binary tree the disregards duplicates- O(nlog(n)). Następnie wyodrębnij je wszystkie z powrotem w tablicy, wykonując przemierzanie - O(n). Zakładam, że nie potrzebujesz konserwacji zamówienia.

Użyj filtra bloom do haszowania. Zmniejszy to znacznie obciążenie pamięci.

W 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

Utwórz, BinarySearchTreektóry ma złożoność O (n).

Najpierw należy utworzyć tablicę, w check[n]której n jest liczbą elementów tablicy, które mają być wolne od duplikatów i ustawić wartość każdego elementu (tablicy kontrolnej) na równą 1. Używając pętli for, przemierza tablicę za pomocą funkcji duplikaty, powiedzmy, że ma na imię arr, a w pętli for zapisz to:

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

Dzięki temu każdy duplikat jest równy zeru. Pozostaje więc tylko przejść przez arrtablicę i wydrukować wszystko, co nie jest równe zeru. Porządek pozostaje i trwa liniowo (3 * n).

Mając tablicę n elementów, napisz algorytm, który usunie 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 tablica wyjściowa jest utrzymywana za pomocą „klucza”. Rozważmy, że klucz ma długość O (n), czas potrzebny na wykonanie sortowania na kluczu i wartość wynosi O (nlogn). Zatem czas potrzebny do usunięcia wszystkich duplikatów z tablicy wynosi O (nlogn).

oto, co mam, chociaż źle umieszcza kolejność, w jakiej 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ę DataStructure, która mogłaby 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;