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:

The value k is positive and will always be smaller than the length of the sorted array.

Length of the given array is positive and will not exceed 104

Absolute value of elements in the array and x will not exceed 104

https://leetcode.com/problems/find-k-closest-elements/description/

Thoughts

首先注意审题，是找与x 值 最相近的k个元素而不是位置最近的k个。 排好序找某值，直接想到二分法。接着找k个相近的，问题和2sum类似，想到用两个指针比大小移动。 移动指针的初始条件和边界条件要注意，而且是先判断下个元素该往哪移再i++或j--。

Code

class Solution {
    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int start = 0, end = arr.length - 1;
        while (start < end) {
            int mid = start + (end - start) / 2;
            if (arr[mid] < x) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        List<Integer> res = new ArrayList<>();
        int i = start - 1, j = start;
        for (int count = k; count > 0 && (i >= 0 || j < arr.length) ; count--) {
            int a = i >= 0 ? Math.abs(arr[i] - x) : Integer.MAX_VALUE;
            int b = j < arr.length ? Math.abs(arr[j] - x) : Integer.MAX_VALUE;
            if (a <= b) {
                i--;
            } else {
                j++;
            }
        }

        for (int p = i + 1; p < j; p++) {
            res.add(arr[p]);
        }

        return res;
    }
}

Analysis

由于要求返回排好序的结果, 让指针最后的位置确定后再把(i, j)加进结果效率比先加再排序好很多.

注意结束时i和j都指向下一个candidate, 因此结果是i和j之间的不包括i, j.

时间复杂度为O(lgn + k)