K Closest Points to Origin
🇷🇺 Название: K Ближайших точек к началу координат
LeetCode: k-closest-points-to-origin
Временная сложность: O(n log n)
Пространственная сложность: O(k)
Решение¶
from typing import List
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
points.sort(key=lambda p: p[0] ** 2 + p[1] ** 2)
return points[:k]
🇺🇸 Условие¶
Given an array of points
where \(points[i] = [x_{i}, y_{i}]\) represents a point on the X-Y plane and an integer k
, return the k
closest points to the origin (0, 0)
.
The distance between two points on the X-Y plane is the Euclidean distance (i.e., \(\sqrt{(x1 - x2)^2 + (y1 - y2)^2}\)).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
🇷🇺 Условие¶
Примеры¶
Example 1:
Input: points = [ [1,3],[-2,2] ], k = 1
Output: [ [-2,2] ]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [ [-2,2] ].
Example 2:
Input: points = [ [3,3],[5,-1],[-2,4] ], k = 2
Output: [ [3,3],[-2,4] ]
Explanation: The answer [ [-2,4],[3,3] ] would also be accepted.
{
"examples": [
{
"input": {
"points": [
[1,3],
[-2,2]
],
"k": 1
},
"output": [
[-2,2]
]
},
{
"input": {
"points": [
[3,3],
[5,-1],
[-2,4]
],
"k": 2
},
"output": [
[3,3],
[-2,4]
]
}
]
}
Ограничения¶
- \(1 \leq k \leq points.length \leq 10^4\)
- \(-10^4 \leq x_{i}, y_{i} \leq 10^4\)
Потребление ресурсов¶
⏱ Time complexity: O(n log n)
¶
points.sort(...)
- Сортировка массива из
n
точек по значениюx² + y²
- В Python
list.sort()
реализован как Timsort:O(n log n)
- Каждый вызов
key(...)
—O(1)
(арифметика фиксированная) - Всего:
O(n log n)
- Сортировка массива из
points[:k]
- Срез первых
k
элементов:O(k)
- Срез первых
Итог: O(n log n + k) = O(n log n), если k < n
🧠 Space complexity: O(k)
¶
- Сортировка
- Python использует Timsort, который работает на месте:
- Никакие копии массива не создаются
- Только временные буферы →
O(log n)
максимум (в стеке и сортировке)
- Но: если
points
изначально не должен меняться, и ты делаешьsorted(points)
— будетO(n)
на копию.
- Python использует Timsort, который работает на месте:
points[:k]
- Возвращает новый список длины
k
→O(k)
- Возвращает новый список длины
Итог: O(k + log n) = O(k)
medium array math divide-and-conquer geometry sorting heap-priority-queue quickselect
Metadata
- title_rus: K Ближайших точек к началу координат
- difficulty: Medium
- leetcode_url: https://leetcode.com/problems/k-closest-points-to-origin/
- topics: ['Array', 'Math', 'Divide and Conquer', 'Geometry', 'Sorting', 'Heap (Priority Queue)', 'Quickselect']
- time: O(n log n)
- space: O(k)
- grind75: True
- tags: ['Array', 'Divide and Conquer', 'Geometry', 'Heap (Priority Queue)', 'Math', 'Medium', 'Quickselect', 'Sorting', 'problem']
- git_revision_date_localized: 5 июля 2025 г.
- git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_revision_date_localized_tag:
- git_revision_date_localized_raw_date: 5 июля 2025 г.
- git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_revision_date_localized_raw_iso_date: 2025-07-05
- git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_revision_date_localized_raw_timeago:
- git_revision_date_localized_raw_custom: 05. июля 2025
- git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
- git_site_revision_date_localized_tag:
- git_site_revision_date_localized: 5 июля 2025 г.
- git_site_revision_date_localized_raw_date: 5 июля 2025 г.
- git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
- git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
- git_site_revision_date_localized_raw_iso_date: 2025-07-05
- git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
- git_site_revision_date_localized_raw_timeago:
- git_site_revision_date_localized_raw_custom: 05. июля 2025