JalanJiang/leetcode-notebook

973. 最接近原点的 K 个点

JalanJiang opened this issue · 4 comments

JalanJiang commented
JalanJiang commented

解一：排序

  1. 算出距离值
  2. 排序
  3. 取最小的 K 个
class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        distance = []
        res = []
        for i in range(len(points)):
            point = points[i]
            dis = point[0]**2 + point[1]**2
            distance.append([i, dis])
            
        distance.sort(key=lambda x:x[1])
        # print(distance)
        
        for i in range(K):
            res.append(points[distance[i][0]])
        return res

上面代码写的比较啰嗦，用列表生成式简化一下：

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        points.sort(key=lambda x: x[0]**2 + x[1] ** 2)
        return points[:K]
JalanJiang commented

解二：堆排序

from heapq import heappush, heappop 

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        queue = []
        distance = lambda x: points[x][0]**2 + points[x][1]**2
        length = len(points)
        for i in range(length):
            heappush(queue, (distance(i), points[i]))
        res = []
        for i in range(K):
            res.append(heappop(queue)[1])
        return res
JalanJiang commented

解三：分治快速选择

快速排序的思路。不同之处在于下次递归划分时：

  • 如果左半边的数的数目 left >= K，那么继续对左半边进行排序，无需关注右半边
  • 如果左半边的数的数目 left < K，那么需要对右半边进行排序，且在右半边中需要前 K - left 个数有序

Python

class Solution:
    def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
        # 计算欧几里得距离
        distance = lambda i: points[i][0] ** 2 + points[i][1] ** 2
        
        def work(i, j, K):
            if i > j:
                return
            # 记录初始值
            oi, oj = i, j
            # 取最左边为哨兵值
            pivot = distance(oi)
            while i != j:
                while i < j and distance(j) >= pivot:
                    j -= 1
                while i < j and distance(i) <= pivot:
                    i += 1
                if i < j:
                    # 交换值
                    points[i], points[j] = points[j], points[i] 
                
            # 交换哨兵
            points[i], points[oi] = points[oi], points[i]
            
            # 递归
            if K <= i - oi + 1:
                # 左半边排序
                work(oi, i - 1, K)
            else:
                # 右半边排序
                work(i + 1, oj, K - (i - oi + 1))
                
        work(0, len(points) - 1, K)
        return points[:K]

PHP

PHP 是世界上最啰嗦的语言。

class Solution {

    /**
     * @param Integer[][] $points
     * @param Integer $K
     * @return Integer[][]
     */
    function kClosest($points, $K) {
        $length = count($points);
        $this->quickSelect($points, 0, $length - 1, $K);
        // var_dump($points);
        return array_slice($points, 0, $K);
    }
    
    // 快速选择
    function quickSelect(&$points, $i, $j, $k) {
        
        // 递归结束条件
        if ($i > $j) {
            return;
        }
        
        $begin = $i;
        $end = $j;
        // 哨兵
        $pivot = $this->getDistance($points, $begin);
        
        while ($i != $j) {
            while ($i < $j && $this->getDistance($points, $j) >= $pivot) {
                $j--;
            }
            while ($i < $j && $this->getDistance($points, $i) <= $pivot) {
                $i++;
            }
            if ($i < $j) {
                // 交换
                $tmp = $points[$i];
                $points[$i] = $points[$j];
                $points[$j] = $tmp;
            }
        }
        
        // 交换哨兵
        $tmp = $points[$begin];
        $points[$begin] = $points[$i];
        $points[$i] = $tmp;
        
        // 递归
        if ($i - $begin + 1 >= $k) {
            $this->quickSelect($points, $begin, $i - 1, $k);
        } else {
            $this->quickSelect($points, $i + 1, $end, $k - ($i - $begin + 1));
        }
    }
    
    // 计算欧几里得距离
    function getDistance($points, $x) {
        return $points[$x][0]*$points[$x][0] + $points[$x][1] * $points[$x][1];
    }
}

知识点

官方题解 该解法是超时的，写一个 Java 版把它 KO 掉 @csming1995 。