K Closest Points to Origin

Q: Quelle est la complexité temporelle des K points les plus proches de l’origine ?

Trier tous les points prend O(n log n) . La version avec un tas a une complexité de O(n log k) pour le parcours, plus O(k log k) pour ordonner les k points retenus, et ne conserve que O(k) points en mémoire.

Q: Avez-vous besoin de la racine carrée pour comparer des distances ?

Non. Pour les nombres qui ne sont pas négatifs, a < b exactement lorsque √a < √b , donc x² + y² donne le même ordre que la distance. Cela reste également un entier : au plus 2 × 10^8 ici, dans la plage des nombres sur 32 bits.

Q: Peut-on résoudre le problème des K points les plus proches de l’origine en O(n) ?

En moyenne, oui. Quickselect partitionne les points autour d’un pivot aléatoire selon le même ordre (x² + y², x, y) et ne continue que du côté qui contient la position k , en O(n) en moyenne. Les k points situés avant cette position constituent la réponse ; les trier ajoute O(k log k) .

MoyenTas Tri

+10

Vous avez n points dans un plan : le point i est (xs[i], ys[i]). Renvoyez les k points les plus proches de l’origine (0, 0), chacun sous la forme d’une paire [x, y].

Ordonnez la réponse par distance à l’origine, du plus proche au plus éloigné. Pour les points à la même distance, placez d’abord celui dont x est le plus petit, puis celui dont y est le plus petit. Un point répertorié plusieurs fois compte une fois par occurrence.

Fonction

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

xsinteger-array: la coordonnée x de chaque point
ysinteger-array: la coordonnée y de chaque point
kinteger: combien de points renvoyer
Renvoieinteger-2d-array: les k points les plus proches sous forme de paires [x, y], du plus proche au plus éloigné, les ex æquo étant départagés selon x puis y

Contraintes

n == xs.length == ys.length
1 ≤ k ≤ n ≤ 5000
-10⁴ ≤ xs[i], ys[i] ≤ 10⁴
Les points peuvent se répéter ; chaque occurrence constitue un point distinct.

Exemples

Entrée: xs = [3, -1, 2, 0]ys = [1, 2, -2, 5]k = 2
Sortie: [[-1, 2], [2, -2]]
Explication: Les distances au carré sont 10, 5, 8 et 25. Les deux plus petites correspondent à (-1, 2) avec 5 et à (2, -2) avec 8, dans cet ordre.

Entrée: xs = [1, -1, 0, 1]ys = [1, 1, 2, -1]k = 3
Sortie: [[-1, 1], [1, -1], [1, 1]]
Explication: (1, 1), (-1, 1) et (1, -1) ont tous une distance au carré de 2, et (0, 2) a une distance au carré de 4. Parmi les points à égalité, (-1, 1) a le plus petit x, et (1, -1) vient avant (1, 1) selon y.

Entrée: xs = [7]ys = [-7]k = 1
Sortie: [[7, -7]]
Explication: Il n’y a qu’un seul point et tu en as besoin d’un, donc la réponse est (7, -7) lui-même.

Pour aller plus loin

Les points arrivent désormais un à la fois, et après chacun d’eux, vous devez indiquer les k plus proches jusqu’à présent. De combien de mémoire avez-vous besoin ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La distance ne nécessite pas de racine carrée : x² + y² donne le même ordre et reste un entier. Tu n’as besoin que de k des n points ; un tas max contenant les k points les plus proches jusqu’ici, avec le plus éloigné au sommet, prêt à être remplacé, coûte O(n log k) au lieu d’un tri complet.

Sélectionnez le point le plus proche k fois

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Le premier point de la réponse est le plus proche de tous, le deuxième est le plus proche parmi les autres, et ainsi de suite. Parcourez donc les points k fois, en prenant chaque fois le point qui vient en premier selon (x² + y², x, y) parmi ceux qui n’ont pas encore été pris.

Chaque parcours examine les n points. Pour n = 5000 et k = 2500, cela représente 1.25 × 10^7 comparaisons de triplets.

Algorithme

Marquez chaque point comme non pris.
Répétez k fois : parcourez les points non pris et trouvez celui qui vient en premier selon (x² + y², x, y).
Marquez-le comme pris et ajoutez [x, y] à la réponse.
Renvoyez la réponse.

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

Trier chaque point

Intuition

La réponse correspond aux premiers k points de l’ordre complet. Il faut donc trier chaque point selon (x² + y², x, y) et garder les premiers k. Dans l’exemple 1, les clés triées sont (5, -1, 2), (8, 2, -2), (10, 3, 1) et (25, 0, 5), et les deux premières donnent la réponse.

Le tri coûte O(n log n), quelle que soit la valeur de k. Lorsque k est petit, une grande partie de ce travail sert à ordonner des points qui ne feront jamais partie de la réponse.

Algorithme

Construis la clé de chaque point (x² + y², x, y).
Trie les points par clé.
Retourne les k premiers sous forme de paires [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]]

Conserver les k plus proches dans un tas maximum

Intuition

Conserve les meilleurs points k vus jusqu’à présent. Un nouveau point ne peut évincer que le point conservé qui occupe le dernier rang ; stocke donc les points conservés dans un tas max selon (x² + y², x, y), avec ce point au sommet. Une fois k points stockés, un point mieux classé que celui au sommet le remplace ; tout autre point est écarté, car les k points stockés sont déjà mieux classés que lui.

Dans l’exemple 2 avec k = 3, le sommet après les trois premiers points est (0, 2), avec la clé (4, 0, 2). Le point (1, -1) a pour clé (2, 1, -1), est mieux classé et le remplace.

Un tas n’est que partiellement trié ; retire donc le sommet k fois et remplis la réponse de la dernière position à la première. Le coût pour chaque point est d’au plus une étape dans le tas en O(log k) ; la complexité temporelle est donc O(n log k) et la mémoire utilisée est de O(k).

Algorithme

Créez un tas maximum vide, dont les clés sont (x² + y², x, y).
Insérez chacun des k premiers points.
Pour chaque point suivant, comparez-le à l’élément au sommet : s’il est mieux classé, remplacez celui-ci par ce point et faites-le descendre dans le tas ; sinon, ignorez-le.
Retirez l’élément au sommet k fois ; chaque point retiré remplit la dernière case libre du résultat.
Renvoyez le résultat.

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

Pièges et cas limites

Ignorer le départage. Dans l’exemple 2, trois points sont à une distance de 2 ; sans comparer x, puis y, ils apparaissent dans l’ordre d’entrée au lieu de (-1, 1), (1, -1), (1, 1).
Conserver un tas min de k points. Son sommet est le point le plus proche, donc chaque éviction élimine un point dont la réponse a besoin, et il ne reste que les k points les plus éloignés.
Lire directement la réponse dans le tableau du tas. Ce tableau n’est que partiellement ordonné ; retirez d’abord les points un par un.
Supprimer les points répétés. Si (5, 5) apparaît trois fois et que k = 3, la réponse contient ce point trois fois.

Questions fréquentes4

Quelle est la complexité temporelle des K points les plus proches de l’origine ?

Trier tous les points prend O(n log n). La version avec un tas a une complexité de O(n log k) pour le parcours, plus O(k log k) pour ordonner les k points retenus, et ne conserve que O(k) points en mémoire.

Pourquoi utiliser un tas max plutôt qu’un tas min pour les k points les plus proches ?

Un nouveau point est en compétition avec le plus éloigné des k points conservés ; ce point doit donc se trouver au sommet. Un tas min ne fonctionne que s’il contient les n points, afin que tu puisses supprimer les k plus proches, ce qui nécessite une mémoire de O(n) au lieu de O(k).

Avez-vous besoin de la racine carrée pour comparer des distances ?

Non. Pour les nombres qui ne sont pas négatifs, a < b exactement lorsque √a < √b, donc x² + y² donne le même ordre que la distance. Cela reste également un entier : au plus 2 × 10^8 ici, dans la plage des nombres sur 32 bits.

Peut-on résoudre le problème des K points les plus proches de l’origine en O(n) ?

En moyenne, oui. Quickselect partitionne les points autour d’un pivot aléatoire selon le même ordre (x² + y², x, y) et ne continue que du côté qui contient la position k, en O(n) en moyenne. Les k points situés avant cette position constituent la réponse ; les trier ajoute O(k log k).

def kClosest(xs, ys, k):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

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

Résultat attendu

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

K Closest Points to Origin

Fonction

Contraintes

Exemples

Indices

Solution

Sélectionnez le point le plus proche k fois

Trier chaque point

Conserver les k plus proches dans un tas maximum

Pièges et cas limites

Questions fréquentes4

Problèmes similaires