658. Find K Closest Elements

leetcode

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
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        while (arr.size() > k) {
            if (x - arr.front() > arr.back() - x) {
                // 如果 x - arr.front() 的差大於 arr.back() - x 的話
                // 代表 arr.front() 離中心點 x 比較遠
                // 這時候就 erase 前面
                arr.erase(arr.begin());
            } else {
                // 如果 arr.back() - x 的差大於 x - arr.front() 的話
                // 代表 arr.back() 離中心點 x 比較遠
                // 這時候就 pop_back() 後面
                arr.pop_back();
            }
        }
        return arr;
    }
};
  • T: O(log⁡(N)+K)O(\log(N) + K)
  • S: O(1)O(1)