K Closest Points to Origin

Q: Jaka jest złożoność czasowa problemu K najbliższych punktów względem początku układu współrzędnych?

Posortowanie wszystkich punktów zajmuje O(n log n) . Wersja z kopcem wymaga O(n log k) podczas przeglądania oraz O(k log k) do uporządkowania k pozostałych punktów, a w pamięci przechowuje tylko O(k) punktów.

Q: Dlaczego do znalezienia k najbliższych punktów używamy kopca maksymalnego, a nie kopca minimalnego?

Nowy punkt konkuruje z najdalszym spośród k zachowanych punktów, więc ten punkt musi znajdować się na szczycie. Kopiec minimalny działa tylko wtedy, gdy przechowuje wszystkie n punktów, aby można było usunąć k najbliższych, co wymaga O(n) pamięci zamiast O(k) .

Q: Czy potrzebujesz pierwiastka kwadratowego, aby porównać odległości?

Nie. Dla liczb, które nie są ujemne, a < b wtedy i tylko wtedy, gdy √a < √b , więc x² + y² daje tę samą kolejność co odległość. Wynik pozostaje też liczbą całkowitą: w tym przypadku wynosi najwyżej 2 × 10^8 , czyli mieści się w zakresie 32-bitowym.

Q: Czy problem K najbliższych punktów względem początku układu współrzędnych można rozwiązać w czasie O(n)?

Średnio tak. Quickselect dzieli punkty względem losowego elementu osiowego w tej samej kolejności (x² + y², x, y) i kontynuuje tylko po tej stronie, po której znajduje się pozycja k , co średnio zajmuje O(n) . Odpowiedzią jest k punktów znajdujących się przed tą pozycją; ich sortowanie dodaje O(k log k) .

ŚrednieKopiec Sortowanie

+10

Dostajesz n punktów na płaszczyźnie: punkt i ma współrzędne (xs[i], ys[i]). Zwróć k punktów najbliższych początkowi układu współrzędnych (0, 0), każdy jako para [x, y].

Uporządkuj odpowiedź według odległości od początku układu współrzędnych, zaczynając od najbliższego punktu. Punkty w tej samej odległości uporządkuj najpierw rosnąco według x, a następnie według y. Punkt występujący na liście więcej niż raz liczy się osobno za każdym wystąpieniem.

Funkcja

kClosest(xs: integer-array, ys: integer-array, k: integer) → integer-2d-array

xsinteger-array: współrzędna x każdego punktu
ysinteger-array: współrzędna y każdego punktu
kinteger: ile punktów zwrócić
Zwracainteger-2d-array: k najbliższych punktów jako pary [x, y], od najbliższego, a w przypadku remisów według x, a następnie y

Ograniczenia

n == xs.length == ys.length
1 ≤ k ≤ n ≤ 5000
-10⁴ ≤ xs[i], ys[i] ≤ 10⁴
Punkty mogą się powtarzać; każda kopia jest osobnym punktem.

Przykłady

Wejście: xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
Wyjście: [[-1, 2], [2, -2]]
Wyjaśnienie: Kwadraty odległości wynoszą 10, 5, 8 i 25. Dwie najmniejsze wartości odpowiadają kolejno punktom (-1, 2) z wartością 5 i (2, -2) z wartością 8.

Wejście: xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
Wyjście: [[-1, 1], [1, -1], [1, 1]]
Wyjaśnienie: (1, 1), (-1, 1) i (1, -1) mają kwadrat odległości równy 2, a (0, 2) ma 4. Spośród punktów z takim samym wynikiem (-1, 1) ma najmniejszą współrzędną x, a (1, -1) jest przed (1, 1) pod względem y.

Wejście: xs = [7]ys = [-7]k = 1
Wyjście: [[7, -7]]
Wyjaśnienie: Jest tylko jeden punkt i potrzebujesz jednego, więc odpowiedzią jest sam punkt (7, -7).

Pytanie dodatkowe

Punkty będą teraz pojawiać się pojedynczo, a po każdym z nich musisz podać k najbliższych punktów spośród dotychczas otrzymanych. Ile pamięci potrzebujesz?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Odległość nie wymaga pierwiastka kwadratowego: x² + y² daje tę samą kolejność i pozostaje liczbą całkowitą. Potrzebujesz tylko k z n punktów, więc kopiec maksymalny zawierający k dotychczas najbliższych punktów, z najdalszym na szczycie, gotowym do zastąpienia, ma koszt O(n log k) zamiast pełnego sortowania.

Wybierz najbliższy punkt k razy

Poprawne, ale nie kończy się na największych testach

Intuicja

Pierwszy punkt odpowiedzi jest najbliższy ze wszystkich, drugi jest najbliższy spośród pozostałych i tak dalej. Przeskanuj więc punkty k razy, za każdym razem wybierając spośród jeszcze niewybranych ten punkt, który ma najmniejszą wartość (x² + y², x, y).

Każde skanowanie obejmuje wszystkie n punktów. Dla n = 5000 i k = 2500 daje to 1.25 × 10^7 porównań trójelementowych.

Algorytm

Oznacz każdy punkt jako niewybrany.
Powtórz k razy: przejrzyj niewybrane punkty i znajdź ten, który jest pierwszy według (x² + y², x, y).
Oznacz go jako wybrany i dodaj [x, y] do odpowiedzi.
Zwróć odpowiedź.

def kClosest(xs, ys, k):
    n = len(xs)
    taken = [False] * n
    result = []
    for _ in range(k):
        best = -1
        for i in range(n):
            # Compare (squared distance, x, y): the order the answer uses.
            if not taken[i] and (best == -1 or
                                 (xs[i] * xs[i] + ys[i] * ys[i], xs[i], ys[i]) <
                                 (xs[best] * xs[best] + ys[best] * ys[best], xs[best], ys[best])):
                best = i
        taken[best] = True
        result.append([xs[best], ys[best]])
    return result

Posortuj każdy punkt

Intuicja

Odpowiedzią jest pierwsze k punktów z pełnego porządku, więc posortuj każdy punkt według (x² + y², x, y) i zachowaj pierwsze k. W przykładzie 1 posortowane klucze to (5, -1, 2), (8, 2, -2), (10, 3, 1) i (25, 0, 5), a pierwsze dwa dają odpowiedź.

Sortowanie kosztuje O(n log n), niezależnie od wartości k. Gdy k jest małe, większość tej pracy polega na porządkowaniu punktów, które nigdy nie trafią do odpowiedzi.

Algorytm

Zbuduj klucz każdego punktu (x² + y², x, y).
Posortuj punkty według klucza.
Zwróć pierwsze k z nich jako pary [x, y].

def kClosest(xs, ys, k):
    points = list(zip(xs, ys))
    # Sort by squared distance, then x, then y: the order the answer uses.
    points.sort(key=lambda p: (p[0] * p[0] + p[1] * p[1], p[0], p[1]))
    return [[x, y] for x, y in points[:k]]

Zachowaj k najbliższych elementów w kopcu maksymalnym

Intuicja

Zachowuj najlepsze dotąd k punktów. Nowy punkt może wyprzeć tylko zachowywany punkt, który zajmuje ostatnie miejsce w rankingu, więc przechowuj zachowywane punkty w kopcu maksymalnym uporządkowanym według (x² + y², x, y), z tym punktem na szczycie. Gdy przechowujesz już k punktów, punkt, który zajmuje wyższe miejsce w rankingu niż ten na szczycie, zastępuje go; każdy inny punkt jest odrzucany, ponieważ k przechowywanych punktów zajmuje już wyższe miejsca w rankingu.

W przykładzie 2 dla k = 3 szczyt po pierwszych trzech punktach to (0, 2) z kluczem (4, 0, 2). Punkt (1, -1) ma klucz (2, 1, -1), zajmuje wyższe miejsce w rankingu i zastępuje go.

Kopiec jest tylko częściowo uporządkowany, więc usuń z niego element ze szczytu k razy i wypełnij odpowiedź od ostatniego miejsca do pierwszego. Obsługa każdego punktu wymaga co najwyżej jednego kroku kopca O(log k), więc czas działania wynosi O(n log k), a pamięć O(k).

Algorytm

Utwórz pustą kopcową kolejkę priorytetową typu max, uporządkowaną według klucza (x² + y², x, y).
Wstaw każdy z pierwszych k punktów.
Dla każdego kolejnego punktu porównaj go z elementem na szczycie: jeśli ma wyższy priorytet, wstaw go zamiast niego i przesiej w dół; w przeciwnym razie pomiń go.
Usuń element ze szczytu k razy; każdy usunięty punkt wypełnia ostatnie wolne miejsce w wyniku.
Zwróć wynik.

import heapq


def kClosest(xs, ys, k):
    # heapq is a min-heap; negating every part of (distance, x, y) puts the
    # farthest kept point, in the answer's order, on top.
    heap = []
    for x, y in zip(xs, ys):
        item = (-(x * x + y * y), -x, -y)
        if len(heap) < k:
            heapq.heappush(heap, item)
        elif item > heap[0]:
            # The new point comes before the farthest kept one: swap them.
            heapq.heapreplace(heap, item)
    # Popping gives the farthest first, so fill the answer from the back.
    result = [None] * len(heap)
    for i in range(len(result) - 1, -1, -1):
        _, x, y = heapq.heappop(heap)
        result[i] = [-x, -y]
    return result

Pułapki i przypadki brzegowe

Pominięcie rozstrzygania remisu. W przykładzie 2 trzy punkty znajdują się w odległości 2; bez porównania najpierw x, a następnie y, pojawią się w kolejności wejściowej zamiast jako (-1, 1), (1, -1), (1, 1).
Przechowywanie k punktów w kopcu minimalnym. Jego wierzchołkiem jest najbliższy punkt, więc każde usunięcie odrzuca punkt potrzebny w odpowiedzi, a na końcu zostaje k najdalszych punktów.
Odczytywanie odpowiedzi bezpośrednio z tablicy kopca. Ta tablica jest tylko częściowo uporządkowana; najpierw usuwaj punkty pojedynczo.
Usuwanie powtarzających się punktów. Jeśli punkt (5, 5) występuje trzy razy, a k = 3, odpowiedzią jest ten punkt trzykrotnie.

Najczęstsze pytania4

Jaka jest złożoność czasowa problemu K najbliższych punktów względem początku układu współrzędnych?

Posortowanie wszystkich punktów zajmuje O(n log n). Wersja z kopcem wymaga O(n log k) podczas przeglądania oraz O(k log k) do uporządkowania k pozostałych punktów, a w pamięci przechowuje tylko O(k) punktów.

Dlaczego do znalezienia k najbliższych punktów używamy kopca maksymalnego, a nie kopca minimalnego?

Nowy punkt konkuruje z najdalszym spośród k zachowanych punktów, więc ten punkt musi znajdować się na szczycie. Kopiec minimalny działa tylko wtedy, gdy przechowuje wszystkie n punktów, aby można było usunąć k najbliższych, co wymaga O(n) pamięci zamiast O(k).

Czy potrzebujesz pierwiastka kwadratowego, aby porównać odległości?

Nie. Dla liczb, które nie są ujemne, a < b wtedy i tylko wtedy, gdy √a < √b, więc x² + y² daje tę samą kolejność co odległość. Wynik pozostaje też liczbą całkowitą: w tym przypadku wynosi najwyżej 2 × 10^8, czyli mieści się w zakresie 32-bitowym.

Czy problem K najbliższych punktów względem początku układu współrzędnych można rozwiązać w czasie O(n)?

Średnio tak. Quickselect dzieli punkty względem losowego elementu osiowego w tej samej kolejności (x² + y², x, y) i kontynuuje tylko po tej stronie, po której znajduje się pozycja k, co średnio zajmuje O(n). Odpowiedzią jest k punktów znajdujących się przed tą pozycją; ich sortowanie dodaje O(k log k).

def kClosest(xs, ys, k):
    # Wpisz kod tutaj

Test #1

Test #2

Test #3

Argumenty

xs = [3, -1, 2, 0]
ys = [1, 2, -2, 5]
k = 2

Oczekiwany wynik

[[-1, 2], [2, -2]]

K Closest Points to Origin

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Wybierz najbliższy punkt k razy

Posortuj każdy punkt

Zachowaj k najbliższych elementów w kopcu maksymalnym

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania