LeetCode 658. Find K Closest Elements C++

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
Approach

配列、KとXのセットをあげて、Xの差から最も近いK個はどれですか.2つの差が同じ場合、値が小さい優先ですが、差が異なる場合、差が小さい優先です.この問題は簡単に二分で探して、Xに最も近い値以下の下付きleftを見つけて、それから差が最も近いK個がどんな値なのかを処理しなければならない.この時、ここではtwo pointersの思想を使って、0~left+Kの範囲からK個に縮小することができて、答えです.もちろんleft+Kは境界を越えることに注意して、私達は境界に対して特殊な処理があって、left=0の時、答えは前K個の要素とleft=配列の長さ-1で、答えは後K個の要素で、これはもっと速くなります.

Code

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        if (arr.size() < 2)return arr;
        int left = 0, right = arr.size() - 1, len = arr.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == x) {
                left = mid;
                break;
            }
            if (arr[mid] > x)right = mid - 1;
            else left = mid + 1;
        }
        if (left == 0) {
            return vector<int>(arr.begin(), arr.begin() + k);
        }
        else if (left == arr.size() - 1 ) {
            return vector<int>(arr.end() - k, arr.end());
        }   
        int i = 0, j = left + k1;
        while (j - i +1 > k) {
            int rr = arr[j] - x;
            int ll = x - arr[i];
            if (rr >= ll)j--;
            else i++;
        }
        return vector<int>(arr.begin() + i, arr.begin() + j+1);
    }
};