# 658. Find K Closest Elements

###### tags: `leetcode` `658` `medium` `rewrite` `binary search`

## :memo: Question

## :memo: 題意
:bulb: 給你一個 numslist，給你 k 和 x，那回傳 k 個與 x 靠得最近的數字。

## :memo: My solution
* :medal: 那這題有給你，他有定義怎麼樣是最相近的。
* :medal: 寫題思路

1. caculate the closer value to all value in the arr，and put the original value and coser value in tuple type to the new list.
2. sort the numslist by closer value
3. return sorted(the k value list)

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        closer_value_list = []
        
        
        for i in arr:
            closer_value_list.append((abs(i-x), i))
    
        
        closer_value_list_sort = sorted(closer_value_list, key= lambda x: x[0])
        ans = [data[1] for data in closer_value_list_sort[:k]]

        return sorted(ans)

## :memo: bigO
* 時間複雜度: O(2* nlogn)
* 空間複雜度: O(n)，the space used by solution array.

## :memo: 檢討
* 可以用 binary search，速度更快

## :memo: leetcode solution
* :medal: 用 binary search 找出最相近的那個數字
* :medal: 寫題思路

1. use binary search find the closest number index
2. set the right and left point (closest number index, closest number index+1) and use sliding window to find the answer

class Solution:
    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
        if len(arr) == k:
            return arr
        
        def binarysearch(num, target):
            
            l = 0
            r = len(num) - 1
            
            while l <= r:
                m = (l+r) // 2
                if num[m] == target:
                    return m
                elif num[m] > target:
                    r = m - 1
                else:
                    l = m + 1
                    
            return l
        

        left = binarysearch(arr, x) - 1
        right = left + 1
        
        while right - left - 1 < k:
            
            if left == -1:
                right += 1
                continue

            if right == len(arr) or abs(arr[left] - x) <= abs(arr[right] - x):
                left -= 1
            else:
                right += 1
        
        
        return arr[left+1:right]

## :memo: bigO
* 時間複雜度: O(logn + k)
* 空間複雜度: O(1)，the space used by solution array.