L658 Find K Closest Elements

Binary Search

Problem

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.

最接近x的k个数 取值小的数

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

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

Solution

• TC: O(n)

• right - left >= k : since we only want k elements, if right - left < k, we can't get total of k elements

• arr[left] - x > arr[right] - x, could help us to find out the left index or the right index value is too small or too big.

public List<Integer> find(int[] arr, int k, int x){
    List<Integer> res = new ArrayList<>();
    int left = 0, right = arr.length - 1;
    while(right - left >= k ){
        if(Math.abs(arr[left] - x) > Math.abs(arr[right] - x){
            left++;
        }else{
            right--;
        }
    }
    for(int i = 0; i < k; i++){
        res.add(arr[i]);
    }
    return res;
}