Skip to main content

658. Find K Closest Elements

https://leetcode.com/problems/find-k-closest-elements/

Python​

Custom Sort​

  • 利用abs(x-num)會找出與x的距離的特性
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        nums = sorted(arr, key=lambda num: abs(x-num))
        return sorted(nums[:k]) # Sort it back to ascending order
  • 官方solution，很有趣的做法
  • 改變Binary search的右界，藉以限制其找出來的左界不會造成右界凸出去
class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        left, right = 0, len(arr)-k

        while left < right:
            pivot = (left+right) >> 1
            if x-arr[pivot] > arr[pivot+k]-x:
                left = pivot + 1
            else:
                right = pivot

        return arr[left:left+k]