658 Find K Closest Elements

658. Find K Closest Elements

1. Question

Given a sorted array, two integerskandx, find thekclosest elements toxin 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=3

Output: [1,2,3,4]

Example 2:

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

Output: [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 10^4

3. Absolute value of elements in the array and x will not exceed 10^4

2. Implementation

(1) Binary Search + Two Pointers

思路: 这道题非常多corner cases要注意考虑

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        List<Integer> res = new ArrayList<>();

        if (arr == null || arr.length == 0) {
            return res;
        }

        int n = arr.length;

        if (x <= arr[0]) {
            return getSubArray(res, arr, 0, k - 1);
        }
        else if (x >= arr[n - 1]) {
            return getSubArray(res, arr, n - k, n - 1);
        }
        else {
            int index = binarySearch(arr, x);
            int low = Math.max(0, index - k);
            int high = Math.min(n - 1, index + k);

            while (high - low + 1 > k) {
                if (low < 0 || ((x - arr[low]) <= (arr[high] - x))) {
                    --high;
                }
                else if (high >= n || ((arr[high] - x) < (x - arr[low]))) {
                    ++low;
                }
                else {
                    break;
                }
            }
            return getSubArray(res, arr, low, high);
        }
    }

    public List<Integer> getSubArray(List<Integer> res, int[] arr, int start, int end) {
        for (int i = start; i <= end; i++) {
            res.add(arr[i]);
        }
        return res;
    }

    public int binarySearch(int[] nums, int target) {
        int start = 0, end = nums.length - 1, mid = 0;

        while (start + 1 < end) {
            mid = start + (end - start) / 2;

            if (nums[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return nums[start] >= target ? start : end;
    }
}

3. Time & Space Complexity

Binary Search + Two Pointers: 时间复杂度O(logn + k), 空间复杂度O(k)