×2019-12-18 找到 K 个最接近的元素

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

示例 1:

输入: [1,2,3,4,5], k=4, x=3
输出: [1,2,3,4]

示例 2:

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

说明:

k 的值为正数，且总是小于给定排序数组的长度。
数组不为空，且长度不超过 104
数组里的每个元素与 x 的绝对值不超过 104

更新(2017/9/19):
这个参数 arr 已经被改变为一个整数数组（而不是整数列表）。 请重新加载代码定义以获取最新更改。

C++1

解题思路：
使用二分法，使得两边都逐渐接近x，但是每次下标只会从start增大，保证如果有两个数与 x 的差值一样，优先选择数值较小的那个，也就是左边的数。

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int size = arr.size(); 
// 这个点要选在倒数第k个，因为起始点不可能在这个或者以后，否则end-begin<k找不到k个数了，还有一方面是因为下面要用mid+k判断，否则程序溢出
        int begin = 0, end = size-k, mid=0;
        while(begin<end){
            mid = begin+(end-begin)/2;
            if(abs(arr[mid]-x)>abs(arr[mid+k]-x)){
                begin = mid+1;
            }else{
                end = mid;
            }
        }
        vector<int> res;
        for(int i=begin;i<begin+k;i++){
            res.push_back(arr[i]);
        }
        return res;
    }
};

C++2

解题思路：
从两边向中间缩小范围，直到还剩下k个数为止。

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int size = arr.size();
        int begin = 0, end = size-1;
        while(size>k){
            // 这个等于号不要忘了，当等于的时候要选择保留左边的数
            if(abs(arr[end]-x)>=abs(arr[begin]-x)){
                end--;
            }else{
                begin++;
            }
            size--;
        }
        vector<int>res;
        for (int index = begin; index <=end; index++)
            res.push_back(arr[index]);       

        return res;
    }
};