Algorytm znajdowania 2 elementów z zadaną różnicą w tablicy

Question

Dostaję tablicę liczb rzeczywistych, A. Ma elementy n + 1. Wiadomo, że istnieją co najmniej 2 elementy macierzy x i y takie, że:

abs(x-y) <= (max(A)-min(A))/n 

trzeba utworzyć algorytm znalezienia 2 elementy (w przypadku istnieje więcej, każda para jest dobre) w czasie O (n).

Próbuję od kilku godzin i utknąłem, wszelkie wskazówki/wskazówki?

Answer 1

woo Mam to! Sztuczka polega na tym, że liczby są punktami na linii. Następnie min(A) i max(A) definiują odpowiednio początkowy i końcowy punkt linii. Teraz podziel ten wiersz na n równych odstępach o długości (max(A)-min(A))/n. Ponieważ istnieją punkty n+1, dwa z nich muszą należeć do jednego z przedziałów.

Należy pamiętać, że nie musimy polegać na pytaniu informującym nas, że istnieją dwa punkty, które spełniają kryterium. Jest zawsze dwa punkty, które go spełniają.

Sam algorytm: Możesz skorzystać z uproszczonej formy sortowania wiadra, ponieważ potrzebujesz tylko jednego przedmiotu na wiadro (dwa trafienia i gotowe).Najpierw przeprowadź pętlę raz przez tablicę, aby uzyskać min(A) i max(A) i utworzyć tablicę całkowitą buckets[n] zainicjowaną na pewną wartość domyślną, na przykład -1. Następnie przejdź do drugiego przejazdu:

for (int i=0; i<len; i++) { 
    int bucket_num = find_bucket(array[i]); 
    if (bucket[bucket_num] == -1) 
     bucket[bucket_num] = i; 
    else 
     // found pair at (i, bucket[bucket_num]) 
} 

Gdzie find_bucket(x) Zwraca wynik zaokrąglony w dół całkowitą x/((max(A)-min(A))/n).

Answer 2

Przeformułowmy problem: znajdziemy dwa elementy, takie jak abs(x-y) <= c, gdzie c jest stałą, którą możemy znaleźć w czasie O(n). (Rzeczywiście, możemy obliczyć zarówno max(A) i min(A) w czasie liniowym i po prostu przypisać c=(max-min)/n).

Wyobraźmy sobie, że mamy zestaw wiader, tak, że w pierwszych elementów kubełkowych 0<=x<c umieszczonych w drugich elementów kubełkowych c<=x<=2c umieszczonych itp dla każdego elementu, możemy określić jego wiadro do O(1) czasie. Pamiętaj, że liczba zajętych segmentów nie będzie większa niż liczba elementów w tablicy.

Wykonajmy iterację w tablicy i umieść każdy element w wiadrze. Jeśli w wiadrze będziemy je umieszczać, już jest inny element, to właśnie znaleźliśmy odpowiednią parę x i y!

Jeśli wykonaliśmy iterację całej tablicy, a każdy element wpadł do jej własnego wiadra, nie martw się! Iteruj teraz kubły (nie ma więcej niż n kubełków, jak już powiedzieliśmy powyżej) i dla każdego elementu pojemnika x, jeśli w następnym wiadrze y element jest taki, że abs(x-y)<=c, to znaleźliśmy rozwiązanie.

Jeśli przeszukaliśmy wszystkie wiadra i nie znaleźliśmy odpowiednich elementów, to nie ma rozwiązania. OMG, naprawdę tęskniłem za tymi rzeczami (zobacz the other answer).

Wiadra mogą być zaimplementowane jako mapa skrótów, gdzie każdy pojemnik ma jeden indeks tablicy (umieszczenie elementu w wiadrze będzie wyglądać tak: buckets[ a[i]/c] = i). Obliczamy czas c w czasie O(n), przypisujemy elementy do segmentów w czasie O(n)*O(1) (O(1) jest dostęp do mapy skrótu), przechodzimy do wiader w czasie O(n). Dlatego cały algorytm jest liniowy.