658. Find K Closest Elements

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]

My Solutions:

用二分法找到x的位置。然后从x的左边第k个值、和x的右边第k个值作为一个window，通过比较左右边值谁更closer，把x的左右边值的window缩小，直到window的大小是k。

Time: O(logN)

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int xIndex = findXIndex(arr, x);
        // x的左边和右边可能不够k个值
        int left = xIndex - k < 0 ? 0 : xIndex - k;
        int right = xIndex + k > arr.length - 1 ? arr.length - 1 : xIndex + k;
        while (left + k <= right) {
            if (Math.abs(arr[left] - x) <= Math.abs(arr[right] - x)) right--;
            else left++;
        }
        List<Integer> res = new ArrayList<>();
        for (int i = left; i <= right; i++) res.add(arr[i]);
        return res;
    }

    private int findXIndex(int[] arr, int x) {
        int l = 0, r = arr.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x) return mid;
            else if (arr[mid] < x) l = mid;
            else r = mid;
        }
        // if two adjacent values are same close, return the left one
        if (Math.abs(arr[l] - x) <= Math.abs(arr[r] - x)) return l;
        else return r;
    }
}