Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

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

 

Example 2:

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

 

Note:

1. The value k is positive and will always be smaller than the length of the sorted array.
2. Length of the given array is positive and will not exceed 104
3. Absolute value of elements in the array and x will not exceed 104

 

M1: 找出k个最近的元素 <==> 在原数组中删除n-k个最远的元素

因为数组有序，离x最远的元素肯定在首、尾出现。先把arr元素复制到新的res arraylist里，每次比较首、尾元素与x之差。如果末尾元素与x之差更大，就去掉末尾元素；如果首元素与x之差更大，就去掉首元素。循环结束条件是res的大小 <= k.

时间：O(N)，空间：O(1)

class Solution {    public List
     
       findClosestElements(int[] arr, int k, int x) {        List
      
        res = new ArrayList<>();        for(int i = 0; i < arr.length; i++) {            res.add(arr[i]);        }        if(arr == null || arr.length == 0) return res;                while(res.size() > k) {            if((x - res.get(0)) <= (res.get(res.size() - 1) - x))                res.remove(res.get(res.size() - 1));            else                res.remove(res.get(0));        }        return res;    }}
      
     

 

 

M2: 改进，用binary search（上面的方法太慢了）

定义一个区间，l = 0, r = arr.length - k，每次比较 中点m所在元素与x之差 和 m+k所在元素与x之差，如果 中点m所在元素与x之差 更大，说明m右侧的元素与x之差更小，l = m+1；反之如果 m+k所在元素与x之差 更大，说明m左侧的元素与x之差更小，r = m。最后的l就是所求区间的左边界，返回区间[l, l+k)

时间：O(logN)，空间：O(1)

class Solution {    public List
     
       findClosestElements(int[] arr, int k, int x) {        List
      
        res = new ArrayList<>();        if(arr == null || arr.length == 0) return res;                int l = 0, r = arr.length - k;        while(l < r) {            int m = l + (r - l) / 2;            if((x - arr[m]) > (arr[m+k] - x))                l = m + 1;            else                r = m;        }        for(int i = l; i < l + k; i++) {            res.add(arr[i]);        }        return res;    }}
      
     

 

二刷：

首先用binary search找到 <= target 的最大元素，其下标作为left, right = left + 1

然后从中间往两边找，left, right两个指针，谁小（和target之差小）移谁

time: O(log(n) + k), space: O(1)

class Solution {    public List
     
       findClosestElements(int[] arr, int k, int x) {        int left = 0, right = arr.length - 1;        while(left + 1 < right) {            int mid = left + (right - left) / 2;            if(arr[mid] == x)                left = mid;            else if(arr[mid] > x)                right = mid;            else                left = mid;        }        int tmp;        if(arr[right] <= x) tmp = right;        if(arr[left] <= x) tmp = left;        else tmp = -1;                left = tmp;        right = left + 1;                List
      
        res = new ArrayList<>();        for(int i = 0; i < k; i++) {            if(left >= 0 && right <= arr.length - 1 && Math.abs(arr[left] - x) <= Math.abs(arr[right] - x))                left--;            else if(left >= 0 && right > arr.length - 1)                left--;            else                right++;        }        for(int i = left + 1; i < right; i++) {            res.add(arr[i]);        }        return res;    }}