###### tags: `Leetcode` `medium` `pointer` `sort` `array` `python` `c++`

# 658. Find K Closest Elements

## [題目連結:] https://leetcode.com/problems/find-k-closest-elements/description/

## 題目:
Given a **sorted** integer array ```arr```, two integers ```k``` and ```x```, return the ```k``` closest integers to ```x``` in the array. The result should also be sorted in ascending order.

An integer ```a``` is closer to ```x``` than an integer ```b``` if:

* ```|a - x| < |b - x|```, or
* ```|a - x| == |b - x|``` and ```a < b```

**Example 1:**

Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]

**Example 2:**

Input: arr = [1,2,3,4,5], k = 4, x = -1
Output: [1,2,3,4]

## 解題想法:
* 此題為給一數組，找出數組中離x最近的k個元素
* 該數組為已排序的

* 使用pointer概念:
* 每次比較數組頭尾與x的差值
* 誰距離大，刪除誰
* 注意: 題目規定，對於|a - x| == |b - x| and a < b，為a比b更近於x，要刪b

* 網上高手解法使用二分法，本人尚未研究請見諒~

## Python:

class Solution(object):
    def findClosestElements(self, arr, k, x):
        """
        :type arr: List[int]
        :type k: int
        :type x: int
        :rtype: List[int]
        """
        #因為已排好
        #從左右兩個方向向中間遍歷
        #每次找距離最遠的數字pop
        #最後保留k個
        while len(arr)>k:
            if x-arr[0]<=arr[-1]-x: #右邊距離遠
                arr.pop() #移除右邊
            else:
                arr.pop(0) #移除左邊
        return arr

result=Solution()
ans=result.findClosestElements(arr = [1,2,3,4,5], k = 4, x = 3)
print(ans)

## C++:

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        vector<int> res=arr;
        while (res.size()>k){
            if ((x-res.front())<=(res.back()-x))
                res.pop_back();
            else
                res.erase(res.begin());
        }
        return res;
    }
};