64. K Closest Points to Origin

8203 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ

  • 平面上に点リストがある場合、原点(0,0)からKまでの点リストを順次出力します.
  • 平面上の2点の距離はユークリッド距離である.



    • ユークリッド距離の優先キュー順序

    

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = x ** 2 + y ** 2
            heapq.heappush(heap, (dist, x, y))
            
        result = []
        for _ in range(k):
            (dist, x, y) = heapq.heappop(heap)
            result.append((x, y))
        return result

  • ユークリッド距離(Euclidean Distance)は、ユークリッド空間における2点間の距離を計算する最も一般的な方法の1つであり、式は以下の通りである.


  • 例えば、原点(0,0)をx座標と呼ぶ場合、(1,3)中のy座標からのユークリッド距離は√(0−1)2+(0−3)2であり、この値は√10、約3.16である.
  • この値は大きさ順にk回抽出すればよいという難解な問題ではない.
  • k回の抽出語では,優先順位キューが直ちに思い出される.
  • ユークリッド距離を計算し,この値を優先キューとしてk回出力すれば,容易に問題を解決できる.
  • mathモジュールを用いて、上記のユークリッド距離式の計算を実現し、hipを挿入した.

  • Pythonのheapqモジュールは最小hipであるため,出力距離が近い順序を必要とする問題解に適している.
  • 最も遠い距離を出力する必要がある場合は、-distを挿入する形で負の数に変換して解くことができる.

  • 結果を抽出する時間です.
  • 結果リストでは、臀部から抽出した結果をk回挿入して返せばよい.
    • 

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = math.sqrt((0-x) ** 2 + (0-y) ** 2)
            heapq.heappush(heap, (dist, x, y))
            
        result = []
        for _ in range(k):
            (dist, x, y) = heapq.heappop(heap)
            result.append((x, y))
        return result

  • しかし、ここで距離を計算して、他の場所で使うのではなく、式を簡略化できるはずです.

  • どうせ順番が同じならいいから.

  • したがって、ここではmath.sqrt()を省略してもよい.

  • これにより、不要な計算を低減し、実行速度を速めることができます.
    • Table View Separatorの削除
    getopt_long()の使い方