658. Find K Closest Elements

Link

Solution

Find the index in the array, which arr[index] is the first element greater or equal to x.

Then we decide which elements around the index can add back to the result.

i : start pointer, it shall be index - 1 j : end pointer, it shall be index

The time complexity is O(logn + k).

 public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new LinkedList<>();
        int index = Arrays.binarySearch(arr, x);
        index = (index < 0) ? -(index + 1) : index;
        int j = index, i = index-1;
        while(k > 0){
            if(j >= arr.length || ((i >= 0) && ((arr[j] - x) >= (x - arr[i])))){
                res.add(0, arr[i]);
                i--;   
            }
            else {
                res.add(arr[j]);
                j++;
            }
            k--;
        }
        return res;
   }