658. Find K Closest Elements

658. Find K Closest Elements

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=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 104
3. Absolute value of elements in the array and x will not exceed 104

----------------
Solution #1, O(logN + K)

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left = findClosest(arr, x);
        int right = left + 1;
        int n = arr.length;
        if (left == -1) {
            right = k;
        }else if (left == n) {
            right = n;
            left = n - k - 1;
        }else {
            while (k > 0) {
                if (left >= 0 && right < n) {
                    if (x - arr[left] > arr[right] - x) {
                        right++;
                    }else {
                        left--;
                    }
                }else if (left >= 0) {
                    left--;
                }else {
                    right++;
                }

                k--;
            }
        }
        left++;
        right--;
        
        List<Integer> rt = new ArrayList<>();
        for (int i = left; i <= right; i++) {
            rt.add(arr[i]);
        }
        
        return rt;
    }
    
    private int findClosest(int[] arr, int x) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            if (mid < arr.length - 1 && arr[mid] <= x && arr[mid + 1] > x) return mid;
            if (arr[mid] > x) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

Solution #2, O(logN + K)，ref：https://leetcode.com/problems/find-k-closest-elements/discuss/106419/O(log-n)-Java-1-line-O(log(n)-+-k)-Ruby
二分查找subarray的起点，用反证法可以证明此算法的正确性

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