# **Leetcode筆記(K Closest Points to Origin)**
:::info
:information_source: 題目 : K Closest Points to Origin, 類型 : heap , 等級 : medium
日期 : 2023/06/07，2023/07/08，2024/02/15
:::
### 嘗試
2023/07/08
- 時間複雜度：
- 形成list過程的時間複雜度為 O(N)，其中 N 是 `points` 列表的長度。
- 不斷從 `maxHeap` 中彈出最大的元素，直到堆中的元素個數等於 k。每次彈出操作的時間複雜度為 O(log N)，並操作(N - k)次。
- 存儲在 `res` 列表中。時間複雜度為 O(k)。
- 因此，整個過程的時間複雜度為 O(N + (N - k) log N)。
- 空間複雜度：
- 在 `maxHeap` 需要的額外空間是 O(N)。
- `res` 列表的大小是 k，所以需要的額外空間是 O(k)。
```python
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
maxHeap = []
for x, y in points:
dis = - (x ** 2 + y ** 2)
maxHeap.append([dis, x, y])
heapq.heapify(maxHeap)
while len(maxHeap) > k:
heapq.heappop(maxHeap)
res = [[x, y] for dis, x, y in maxHeap]
return res
```
使用了quick select
- 時間複雜度：
- 在 `quickSelect` 方法中，通過呼叫 `partition` 方法將陣列切割為兩部分，這個過程的時間複雜度為 O(N)，其中 N 是陣列的長度。
- 在最壞情況下，**`quickSelect`** 方法的時間複雜度為 O(N^2)，但**平均情況下的時間複雜度為 O(N)**。
- **快速選擇並不遞歸訪問雙邊，而是只遞歸進入一邊的元素中繼續尋找。這降低了平均時間複雜度，從O(n log n)至O(n)**
- 最後返回 `points[:k]`，需要 O(k) 的時間複雜度。
- 綜合起來，整個演算法的時間複雜度為 O(N + k)。
- 空間複雜度：
- 演算法僅使用了常數級別的額外空間，沒有使用額外的資料結構。
- 因此，空間複雜度為 O(1)。
```python
from typing import List
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
self.quickSelect(points, 0, len(points) - 1, k)
return points[:k]
def quickSelect(self, points: List[List[int]], start: int, end: int, k: int) -> None:
if start >= end: # 代表list為空或只剩一個元素
return
# 基準點
pivot_index = self.partition(points, start, end)
if pivot_index == k:
return
elif pivot_index < k:
self.quickSelect(points, pivot_index + 1, end, k)
else:
self.quickSelect(points, start, pivot_index - 1, k)
# 最後數組會是 : 小於pivot的在左 大於pivot的在右
def partition(self, points: List[List[int]], start: int, end: int) -> int:
pivot = points[end] # 選定一數為pivot
i = start - 1
for j in range(start, end): # 遍歷這個區間
if self.compare(points[j], pivot) <= 0: # 代表當前元素points[j] 小於pivot
i += 1
points[i], points[j] = points[j], points[i] # 比較小的被放到i上
# 如果當前元素points[j] 大於pivot 則甚麼都不發生
points[i+1], points[end] = points[end], points[i+1] # 最後要把end移到中間 當作分界
return i + 1 # 回傳被分的中界點
def compare(self, point1: List[int], point2: List[int]) -> int:
dist1 = point1[0]**2 + point1[1]**2
dist2 = point2[0]**2 + point2[1]**2
return dist1 - dist2
# dist1 < dist2 -> 回傳負數
# dist1 = dist2 -> 回傳0
# dist1 > dist2 -> 回傳正數
```
2024/02/15
```python
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
minHeap = []
for x, y in points:
minHeap.append((self.distance(x, y), x, y))
heapq.heapify(minHeap)
res = []
while k:
dist, x, y = heapq.heappop(minHeap)
res.append([x, y])
k -= 1
return res
def distance(self, x, y):
return (x ** 2 + y ** 2) ** (1/2)
```
---
### **優化**
[這篇](https://mp.weixin.qq.com/s/FFsvWXiaZK96PtUg-mmtEw)透徹解說topK
時間複雜度：
- 將每個點的距離和坐標存入最小堆的過程，時間複雜度為O(nlogn)，其中n是points的長度。
- 從最小堆中取出k個最小距離的點的過程，時間複雜度為O(klogn)。
總時間複雜度為O(nlogn + klogn) = O((n+k)logn)。
空間複雜度：
- 儲存最小堆的空間複雜度為O(n)。
- 儲存結果的空間複雜度為O(k)。
總空間複雜度為O(n + k)。
```python
class Solution:
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
minHeap = []
for r, c in points:
dist = r **2 + c **2
minHeap.append((dist, r, c))
# 由第一個元素排列
heapq.heapify(minHeap) # 轉成heap
res = []
while k > 0:
dist, r, c = heapq.heappop(minHeap)
res.append([r, c])
k -= 1
return res
```
---
**:warning: 錯誤語法**
:::warning
:::
**:thumbsup:學習**
:::success
:::
**思路**
**講解連結**
Provided by. 58沈剑
###### tags: `heap` `medium` `leetcode`
Sign in with Wallet
Connect another wallet