Znajdź wszystkie możliwe odległości z dwóch tablic:

Złożone dwie uporządkowane tablice: A i B o długości N. Każdy element może zawierać liczbę naturalną mniejszą niż M. Określ wszystkie możliwe odległości dla wszystkich elementów kombinacji A i B. W tym przypadku, jeśli A[i] - B[j] < 0, to odległość wynosi M + (A[i] - B[j]).Znajdź wszystkie możliwe odległości z dwóch tablic:

Przykład:

A = {0,2,3} 
B = {1,2} 
M = 5 

Distances = {0,1,2,3,4}

Uwaga: Wiem O(N^2) rozwiązanie, ale muszę szybsze rozwiązanie niż O(N^2) i O(N x M).

Edytuj: Array A, B i Distances zawierają różne elementy.

Źródło

2015-12-15 Karsten Ari Agathon

Odległości mogą nie zawierać duplikatów. –

Nie sądzę, że znajdziesz lepsze niż 0 (MxN), ale oczekuję, że ktoś coś napisze, byłoby ciekawie :) – Netwave

Biorąc pod uwagę, że dane wyjściowe mogą być wartościami "N * M", nie sądzę, że możemy pisać algorytm szybszy niż O (N * M). –

Możesz otrzymać rozwiązanie złożoności O (MlogM) w następujący sposób.

Przygotowanie Ax tablicy o długości M z Ax [i] = 1, jeśli należy do grupy (a inaczej 0)
Przygotowanie macierzy Bx o długości M z Bx [M-1-j] = 1, jeśli należy do B (i 0 inaczej)
pomocą szybkiej transformaty Fouriera w celu convolve te 2 sekwencje razem
Sprawdzić układ wyjściowy niezerowe wartości odpowiadają możliwe odległości

należy zauważyć, że FFT jest zwykle wykonywane z liczbami zmiennoprzecinkowymi, więc w ste p 4 prawdopodobnie chcesz przetestować, czy wyjście jest większe niż 0,5, aby uniknąć problemów z hałasem zaokrąglania.

Źródło

2015-12-15 09:59:06

Jaki jest rozmiar wyników w kroku 3? –

Dzięki za odpowiedź, panie Peter. Przyjmuję tę odpowiedź, gdy uda mi się to potwierdzić. Obecnie nie do końca rozumiem FFT. Będę bardzo szczęśliwy, jeśli podasz odniesienie do powiązanego algorytmu FFT. –

To jest trywialne, jeśli używasz Pythona z biblioteką scipy, ponieważ istnieje funkcja [fftconvolve] (http://docs.scipy.org/doc/scipy-0.16.0/reference/generated/scipy.signal.fftconvolve.html), który robi krok 3 dla Ciebie w jednym wierszu :) –

Możliwe do zrobienia ze zoptymalizowanym N * N.

Jeśli przekonwertować do 0 ° C i 1 tablicy 1, gdzie w położeniach, które występują w stosunku wagowym (w zakresie [0..M]. Po przekształcają to tablicę do bitmasks, wielkość tablicy zostanie zmniejszona do 64 razy.

pozwoli wyniki wkładki przez bloki o rozmiarze 64. Złożoność nadal będą N*N ale czas pracy zostanie znacznie zmniejszona. Jak wspomniano przez autora ograniczenie do 50000 a i rozmiarach B i M. liczyć Oczekiwane operacje będą N * N/64 ~ = 4 * 10^7. To minie w 1 s.

Źródło

2015-12-15 10:49:17

Możesz użyć bitu lekarze, aby to osiągnąć. Operacje bituvector na dużych bitwektorach są liniowe w rozmiarze bitvector, ale są szybkie, łatwe do wdrożenia i mogą działać dobrze, biorąc pod uwagę limit rozmiaru 50k.

Inicjalizuj dwa bity bitowe o długości M. Wywołaj te vectA i vectAnswer. Ustaw bitów vectA, które odpowiadają elementom w A. Pozostaw vectAnswer z wszystkimi zerami.

Należy zdefiniować metodę obracania bitwektora za pomocą elementów k (obrócić w dół). Nazwę to obracaniem (vect, k).

Następnie dla każdego elementu b B, vectAnswer = vectAnswer | obróć (vectA, b).

Źródło

2015-12-15 11:06:48 Dave

Znajdź wszystkie możliwe odległości z dwóch tablic:

Odpowiedz

Powiązane problemy