題目

  • 題目連結
  • 目標函式 : kClosest(points, k)
    • Input : points: List[List[int]]、k: int
    • Output : List[List[int]]

解題概念

  • 題意 : 給定一陣列 points，其中
    • points[i] = [x_i, y_i] 表示 X-Y 平面上的一點
    • X-Y 平面上兩點之間的距離是歐幾里德距離 $(\sqrt{(x_1-x_2)^2}+\sqrt{(y_1-y_2)^2})$
  • 需要回傳離原點 (0, 0) 最近的 k 個點 (以任意順序皆可)

我的寫法

  • 想法 : 主要使用 Bubble Sort
    • 在比較的過程中，使用 distance() 去比較兩者的值(即歐幾里德距離)
    • 以距離近到遠排序
    • 最後回傳 points[:k]
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    def kClosest(self, points, k):
        
        def distance(point):
            return math.sqrt(point[0] ** 2 + point[1] ** 2)

        for i in range(len(points)):
            for j in range(i+1, len(points)):
                if distance(points[i]) > distance(points[j]):
                    temp = points[i]
                    points[i] = points[j]
                    points[j] = temp

        return points[:k]
  • 成效 :
    • Time Complexity : Time Limit Exceeded

解答 or 其他優秀寫法 - Part1

  • 想法 : 使用 Max Heap 去整理 points，在中間比較的時候使用歐幾里德距離去比較
  • 實作方法 : 直接使用 heapq 套件，使用其中的 nsmallest(n, iterable, key=None) 方法 (回傳一個包含資料 iterable 中前 n 小元素的 list)，其中包含以下參數 :
    1. n = k : 要回傳前 k 小元素
    2. iterable = points : 對資料 points 進行比較
    3. key = lambda (x, y): x * x + y * y : 為比較的依據，這裡使用 lambda 計算歐幾里德距離去比較
  • 程式碼 : 
    1
    2
    3
    4
    5
    import heapq

    def kClosest(self, points, k):
        
        return heapq.nsmallest(k, points, key = (lambda (x, y): x * x + y * y))
  • 成效 :
    • Time Complexity : $O(n)$
    • Runtime: 569 ms (faster than 82.41%)
    • Memory Usage: 19.7 MB (more than 74.58%)

解答 or 其他優秀寫法 - Part2

  • 想法 : 一樣使用 Max Heap 去整理 points，在中間比較的時候使用歐幾里德距離去比較
  • 實作方法 : 這次改使用手動的方式去操作 Max Heap
    • Heap 內儲存的格式為 (dist, x, y)
      • dist : 為歐幾里德距離，特別的是這裡使用 dist = -(x * x + y * y) 的方式去儲存，進而可以讓 Max Heap 儲存前 k 小的元素
    • 建立一個空間為 k 的 Heap，並依序去判斷 points 的各元素
      • 若插入一元素時發現 Heap 已滿 : 則使用 heapq.heappushpop(heap, (dist, x, y)) (元素放入後執行 Delete-MAX)
      • 若插入一元素時發現 Heap 未滿 : 則使用 heapq.heappush(heap, (dist, x, y)) (元素直接插入到 Heap 中)
    • 最後將 heap 整理成所需格式並回傳
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    import heapq

    def kClosest(self, points, k):
        
        heap = []
        
        for (x, y) in points:
            dist = -(x*x + y*y)
            if len(heap) == k:
                heapq.heappushpop(heap, (dist, x, y))
            else:
                heapq.heappush(heap, (dist, x, y))
        
        return [(x,y) for (dist,x, y) in heap]
  • 成效 :
    • Time Complexity : $O(n\log n)$
    • Runtime: 574 ms (faster than 79.84%)
    • Memory Usage: 20.1 MB (more than 55.33%)