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

92

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.

ejel
źródło
4
Czy musisz zachować kolejność unikalnych numerów?
Douglas Leeder
1
Czy wynik musi zostać zwrócony w oryginalnej tablicy?
Douglas Leeder
1
Zaktualizowałem pytanie. Wynik powinien zostać zwrócony w oryginalnej tablicy. Jednak kolejność sekwencji nie ma znaczenia.
ejel
3
To dość denerwujące, gdy ktoś strofuje swoją odpowiedź na pytanie i inne odpowiedzi. Po prostu bądź cierpliwy, ludzie tam dotrą.
GManNickG
2
Dlaczego hashtable nie są dozwolone? To ograniczenie nie ma sensu.
RBarryYoung

Odpowiedzi:

20

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.

mocy
źródło
3
Jest to proste rozwiązanie i jest więcej niż prawdopodobne, czego dotyczy pytanie do rozmowy kwalifikacyjnej.
Kirk Broadhurst
8
Mogą nawet sprawdzać, czy nie cierpisz z powodu przedwczesnej optymalizacji, chyba że dali ci również ograniczenia w czasie wykonywania! :-)
Trevor Tippins
16
Lol, chociaż zdecydowanie szybciej jest sortować tablicę i pracować na posortowanej. Sortowanie powinno być zapewniane przez API i nie jest to żadna przedwczesna optymalizacja.
ziggystar
2
Czy nie powinno to być while (current <= end) zamiast while (current <end)?
Shail
2
Dlaczego uznano to za właściwą odpowiedź? Jeśli zachowanie porządku nie jest konieczne, to nie lepiej jest po prostu użyć sortowania przez scalanie O (nlogn), a następnie usunąć powtarzające się elementy w O (n) ... całkowita złożoność - O (nlogn), co jest znacznie lepsze niż to rozwiązanie.
Pawan
136

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ę.

ejel
źródło
8
Świetna sugestia, ale będziesz potrzebować trochę księgowości, aby śledzić koniec każdego wyniku scalania. Właściwie zrobiłem to raz i tak, wyeliminowanie duplikatów podczas scalania sprawia, że ​​jest to znacznie szybsze.
Mark Ransom
2
Nie jest jasne, czy dodatkowe miejsce O (N / 2) liczy się jako „struktura danych pomocniczych” zakazana w pytaniu - nie wiem, czy ograniczenie ma na celu ustalenie O (1) dodatkowej przestrzeni, czy po prostu zastrzeżenie, że odpowiedź nie powinna zależeć od implementacji dużej starej struktury danych. Może standardowe scalanie jest w porządku. Ale jeśli nie, najlepsza wskazówka: nie próbuj pisać w wywiadzie sortowania przez scalanie na miejscu, chyba że naprawdę wiesz, co robisz.
Steve Jessop
Świetny pomysł. Ale wymaga, aby pozostałe dane zachowały pierwotną kolejność.
Hardy Feng
4
Artykuł opisujący to, co zasugerowała twoja dziewczyna: dc-pubs.dbs.uni-leipzig.de/files/ ...
Mike B
50

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);
}
dsimcha
źródło
1
Niezwykle fajna, niedoceniana odpowiedź! Podoba mi się pomysł użycia elementu na pozycji 1 jako wartości wartowniczej. Gdybym mógł zrobić kilka drobnych sugestii, należałoby zmienić krok 2, aby uwzględnić „każdy element jest w pozycji odpowiadającej jego hash modulo rozmiar tablicy ” i być może wyjaśnić, że duplikaty, które mają być ustawione na wartownik, to elementy, które mają tę samą wartość (w przeciwieństwie do tego samego skrótu lub tego samego rozmiaru tablicy hash modulo).
j_random_hacker
20

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

Byju
źródło
3
Niezłe. Mam propozycję poprawy. Drugą zagnieżdżoną pętlę można zmienić na for (j = 0; j <NewLength; j ++), a na końcu sprawdzanie można zmienić na if (j == NewLength)
Vadakkumpadath
To była świetna sugestia. Zaktualizowałem kod na podstawie
Twojego
Błąd przynajmniej wtedy, gdy mamy te same wartości w tablicy {1,1,1,1,1,1}. Bezużyteczny kod.
Yuriy Chernyshov
Jaka jest złożoność tego, czyż nie jest to również O (n ^ 2)?
JavaSa
1
Tyle głosów za, ale to nie jest wydajne: jest O (n ^ 2), gdy jest niewiele duplikatów.
Paul Hankin
19

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

carl
źródło
Odpowiedź Jeffa B to tylko O ​​(n). Hash-sety i hash-slowniki to bees knees.
ChrisW
3
ChrisW: zestawy skrótów / słowniki są O (1) tylko wtedy, gdy zakładasz brak kolizji. (Nie mówię, że nie użyłbym ich do tego problemu - prawdopodobnie zrobiłbym to - to tylko błędne twierdzenie, że są naprawdę O (1).)
Laurence Gonsalves,
2
Właściwie, skoro znasz już rozmiar tablicy, możesz zagwarantować O (1). Następnie możesz wymienić kolizje w porównaniu z ilością używanej dodatkowej pamięci.
Vitali
Warto przemyśleć tę opinię - nowo opublikowane warunki problemu powodują, że rozwiązanie Jeffa B.
Mark Ransom
3
Możesz rozwinąć temat „przechodzenie”, ponieważ naiwna metoda wymazywania może dać O (n ^ 2) dla dużej liczby duplikatów.
Mark Ransom
11

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.

Jack V.
źródło
7

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.

Dario
źródło
1
OTOH, dodatkowy kod wymagany do zaimplementowania drzewa sortowania może być mniej wydajny (pamięć) niż proste rozwiązanie i prawdopodobnie jest mniej wydajny w czasie wykonywania dla małych (powiedzmy mniej niż 100 elementów) tablic.
TMN
6

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.

fbrereto
źródło
„Jedynym zastrzeżeniem jest to, że oczekiwany algorytm nie powinien wymagać, aby tablica była najpierw sortowana”.
sbi
2
Nie mówi, że nie możesz posortować tablicy, gdy ją otrzymasz ... Bez użycia sortowania pamięci zewnętrznej O (N) jest to jedyny sposób na zrobienie tego w O (N log N) lub lepszym.
Greg Rogers
Do celów tego problemu nie należy używać standardowych narzędzi bibliotecznych. Jeśli jednak chodzi o sortowanie, im więcej o nim myślę, tym bardziej nie jestem pewien, czy jest w porządku, czy nie.
ejel
1
Myślę, że odpowiedzi odnoszące się do standardowych funkcji C ++ i C ++ są przydatne, nawet jeśli nie odpowiadają na pierwotne pytanie, ponieważ zapewniają bardziej zaokrągloną odpowiedź osobom, które znajdą to pytanie później.
Douglas Leeder
6

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;
    }
}
Jeff B
źródło
Nie jest jasne, czy odpowiedź musi znajdować się w oryginalnej tablicy.
Douglas Leeder
Aby to zrobić bez konieczności tworzenia nowej tablicy, możesz po prostu zastąpić duplikat elementem wyskakującym z końca tablicy i powtórzyć bieżącą pętlę, ponieważ problem nie określa, że ​​kolejność ma znaczenie. Wymaga to dodatkowego sprawdzenia granic, ale jest bardzo wykonalne.
Jeff B
6
To był dobry pomysł, dopóki pytanie nie zostało zredagowane. Twój pomysł do haszowania jest najwyraźniej niezgodny z zasadami.
WCWedin
14
Nie rozumiem, dlaczego ta odpowiedź jest najczęściej głosowana. Jest napisany w perlu i wykorzystuje istotne funkcje niedostępne w C, jak pojawia się pytanie.
LiraNuna
5
pytanie zadane dla kodu c, a nie perla. używanie Perla daje ci tablice skrótów i "push" za darmo. Gdybym mógł to zrobić w scali, po prostu zadzwoniłbyś do input.removeDuplicates, ale wątpię, czy byłby to akceptowalne dla ankieterów :)
Peter Recore
5

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;
}
dsh
źródło
4

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;       
    }
Naren
źródło
Zawodzi przynajmniej przy następnych danych wejściowych: {1,1,1,1,1,1,1} {0,0,0,0,0,1,1,1,1,1,1}
Yuriy Chernyshov
3

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] ;                         
     }
}
kiriloff
źródło
2

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.

Anton Gogolev
źródło
Rzeczywiście - podanie O (n) w celu znalezienia największego elementu nie zwiększyłoby całkowitego kosztu O ().
Douglas Leeder
2

Zobaczmy:

  • O (N) pass, aby znaleźć alokację min / max
  • tablica bitów dla znalezionych
  • O (N) przechodzi zamiana duplikatów do końca.
Douglas Leeder
źródło
Biorąc pod uwagę, że są to tylko liczby całkowite, dla uproszczenia można założyć 32-bitowe i nie zawracać sobie głowy szukaniem min / maks: 2 ^ 32 bity to „tylko” 512 MB, więc znalezienie granic to tylko wykorzystanie pamięci i optymalizacja czasu O (1) (oczywiście, spora optymalizacja w przypadku podanego przykładu). A jeśli są 64-bitowe, nie ma to znaczenia, ponieważ nie wiesz, że min i max nie będą od siebie dalej niż liczba bitów pamięci, którą masz.
Steve Jessop
Pomijając teorię, czy przydzielenie 512 MB nie zajmie więcej czasu niż znalezienie min / max?
LiraNuna
Zależy, ile jest danych i jakie są wartości minimalne / maksymalne. Jeśli patrzysz na więcej niż 512 MB danych wejściowych, prawdopodobnie szybciej jest uniknąć tego dodatkowego przejścia O (N). Oczywiście, jeśli patrzysz na tak dużo danych wejściowych, jest mniej prawdopodobne, że masz wolne 512 MB. W przypadkach, gdy min / max są bliskie 0 / INT_MAX, optymalizacja też nie pomaga. Mówię tylko, że chociaż pierwszy krok oczywiście pomaga w przypadku małych liczb, nie można uniknąć faktu, że ten algorytm używa bitów UINT_MAX w najgorszym przypadku, więc musisz zaplanować to ograniczenie.
Steve Jessop
Możesz mieć rację - w każdym przypadku wyjaśnienie pytania oznacza, że ​​użycie tablicy bitowej jest wyłączone. Zostawię tę odpowiedź na wypadek, gdyby ktoś przyszedł później bez ograniczeń i chciał zobaczyć wszystkie możliwe odpowiedzi.
Douglas Leeder
2

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ę.

David R. Tribble
źródło
1

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;
         }
      }
   }
Dominik
źródło
Jeśli nadpisujesz znalezione duplikaty wartością na końcu tablicy, możesz uniknąć przesunięcia całej tablicy w wewnętrznej pętli for (). To doprowadzi cię do O (n ^ 2) z O (n ^ 3). Moja implementacja C unosi się gdzieś tutaj ...
mocj
Myślałem, że zmiana biegów była częścią wymogu, ale masz oczywiście rację.
Dominik
1
@mocj: Podoba mi się Twoje rozwiązanie, wygląda bardzo elegancko. Ale myślę, że to nie zadziała, jeśli ostatnie dwa elementy są równe, ponieważ przestajesz sprawdzać równość jeden przed ostatnim. (przychodzę tutaj, ponieważ mam zbyt reputację, aby komentować gdziekolwiek indziej :()
Dominik
Masz rację, z tym wyjątkiem, że pierwotny problem stwierdza, że ​​wartości na końcu tablicy są pomijalne. Ponieważ nie zwracasz długości zmodyfikowanej tablicy, rozróżnienie między ostatnią wartością a przedostatnią nie ma znaczenia, gdy te dwie wartości są równe. Gdzie wywołujący interpretuje koniec zwróconej tablicy jako
mocj
1

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.

Charith
źródło
1

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;
RichardLi
źródło
1

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
yupbank
źródło
1
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);
}
    }
user1423581
źródło
arr [i + 1] powinien zgłosić wyjątek ArrayIndexOutOfBoundsException dla ostatniego elementu?
Sathesh
@Sathesh No. Z powodu „<arr.length-1”
GabrielBB,
1

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;
}
wildplasser
źródło
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.

Andy Ross
źródło
2
W modyfikacji pierwotnego pytania tabele skrótów nie są dozwolone. Twoje podejście z dwoma wskaźnikami to jednak dobry sposób na kompaktowanie danych wyjściowych po zidentyfikowaniu duplikatów.
Mark Ransom
0

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.

Ashwin
źródło
0

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

gaurav gupta
źródło
chcesz rozwinąć lub podać odniesienie?
dldnh
0

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

PRABHU SEKAR
źródło
1
Sprawdź to za pomocą danych wejściowycharrayInteger = {100,10,1};
Blastfurnace
0

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

user3727788
źródło
Pytanie nie pozwala na użycie dodatkowej struktury danych.
ejel
0

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

Sharief Muzammil
źródło
Co zrobiliście ze wszystkich śmiałych glifów helper data structure (e.g. hashtable) should not be used?
siwobrody
Niekoniecznie potrzebne. Podkreśliłem je tylko w celu zrozumienia.
Sharief Muzammil
0

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");
}
ashim888
źródło
-1

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;
Mike Blandford
źródło