658

658. Find K Closest Elements (Medium)

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]

 

Constraints:

• 1 <= k <= arr.length
• 1 <= arr.length <= 104
• arr is sorted in ascending order.
• -104 <= arr[i], x <= 104

Related Topics:
Binary Search

Similar Questions:

• Guess Number Higher or Lower (Easy)
• Guess Number Higher or Lower II (Medium)
• Find K-th Smallest Pair Distance (Hard)

Solution 1.

// OJ: https://leetcode.com/problems/find-k-closest-elements/
// Author: github.com/lzl124631x
// Time: O(logN + K)
// Space: O(1)
class Solution {
public:
    vector<int> findClosestElements(vector<int>& A, int k, int x) {
        int N = A.size(), j = lower_bound(begin(A), end(A), x) - begin(A), i = j - 1;
        while (j - i - 1 < k) {
            if (i == -1 || (j < N && abs(A[j] - x) < abs(A[i] - x))) ++j;
            else --i;
        }
        return vector<int>(begin(A) + i + 1, begin(A) + j);
    }
};

Solution 2. Binary Search Left Edge (L < R)

Binary Search (L <= R) doesn't fit this problem because L and R might go out of boundary.

We binary search the left edge.

// OJ: https://leetcode.com/problems/find-k-closest-elements/
// Author: github.com/lzl124631x
// Time: O(log(N - k) + k)
// Space: O(1)
class Solution {
public:
    vector<int> findClosestElements(vector<int>& A, int k, int x) {
        int L = 0, R = A.size() - k;
        while (L < R) {
            int M = (L + R) / 2;
            if (x - A[M] > A[M + k] - x) L = M + 1;
            else R = M;
        }
        return vector<int>(begin(A) + R, begin(A) + R + k);
    }
};