973. K Closest Points to Origin - cocoder39/coco39_LC GitHub Wiki

973. K Closest Points to Origin

T(N) = T(N/2) + O(N) T(N/2) = T(N/4) + O(N/2) ... T(N) = O(N) + O(N/2) + ... = O(N)

quick slection: avg O(N), worst case is O(N^2) eg always pick the largest one as pivot

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        low, high = 0, len(points)-1
        while low < high:
            pivot_idx = random.randint(low, high)
            partition_idx = self.partition(points, low, high, pivot_idx)
            if partition_idx == k - 1:
                return points[:k]
            elif partition_idx < k - 1:
                low = partition_idx + 1
            else:
                high = partition_idx - 1
        
        return points[:k]

    def partition(self, points, low, high, pivot_idx):
        points[high], points[pivot_idx] = points[pivot_idx], points[high]
        partition_idx = low
        for i in range(low, high):
            if self.getDistance(points[i]) <= self.getDistance(points[high]):
                points[partition_idx], points[i] = points[i], points[partition_idx]
                partition_idx += 1
        points[partition_idx], points[high] = points[high], points[partition_idx]
        return partition_idx

    def getDistance(self, point):
        return point[0]**2 + point[1]**2