Skróć czas złożoności wyszukiwania do mniej niż n ^ 2 - algorytm, wyszukiwanie

Problem: mamy ciąg par liczb, takich jak [(10, 20), (30, 10), (30, 40), (20, 10), (90, 80), (40, 30), (50, 60) ]. Wyjście: wydrukuj pary symetryczne w sekwencji. ex (10, 20) (20, 10) (30, 40) (40, 30).

Jestem w stanie rozwiązać ten problem za pomocą dwóch pętli for iprzeszukiwanie każdego elementu w sekwencji dla pary symetrycznej. Ale złożoność to O (n ^ 2). Każda inna metoda lub struktura danych w celu zmniejszenia złożoności czasu?

Odpowiedzi:

Użyj haszowania i możesz to zrobić O(N)

• Zapętl każdą parę (a, b)
  • Sprawdź, czy para (b, a) jest w zestawie
  • Jeśli nie, dodaj parę (a, b) do zestawu
  • Jeśli tak, dodaj do rozwiązania

implementacja Pythona

data = [(10, 20), (30, 10), (30, 40), (20, 10), (90, 80), (40, 30), (50, 60)]

output = {}

for (a, b) in data:
v_min = min(a, b)
v_max = max(a, b)

if not output.has_key((v_min, v_max)):
output[(v_min, v_max)] = 0

output[(v_min, v_max)] += 1

pairs = filter(lambda (v, count): count >= 2, output.items())
print map(lambda ((a, b), count) : ((a, b), (b, a)), pairs)