658. Find K Closest Elements ---M ~~~

Given a sorted array arr, 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: 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 <= 10^4
• Absolute value of elements in the array and x will not exceed 104

 

A:

先找到比 <= x  的最大值, 假设在index  seed。  然后再看看比seed+1 的difference 是否更小。

最后再linearly probe till length k

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int n = arr.size();
        // binary search to find index with bigger value that's <= than x
        int start = 0, end = n-1;
        while(start < end){
            int mid = start + (end - start)/2;
            if(arr[mid]>x){
                end = mid-1;
            }else{ // start = mid, but could cause infinite loop, thus 
                if(arr[mid+1]> x){
                    end = mid;
                }else{
                    start = mid+1;
                }
            }            
        }        
        int seed = start;
        // chec that it is possible that's next is closer
        if(seed+1 < n && abs(arr[seed+1]-x) < abs(arr[seed]-x)){
            seed = seed+1;
        }
        // now linear probe to search.
        start = seed;
        end = seed;
        while(end - start +1 < k){
            if(end==n-1){
                start--;
            }else if(start ==0){
                end++;
            }else{
                long absLeft = abs(long(arr[start-1]) - x);
                long absRight = abs(long(arr[end+1]) - x);
                if(absLeft <= absRight){
                    start--;
                }else{
                    end++;
                }
            }
        }
        vector<int> res(arr.begin()+start, arr.begin()+end+1);
        return res;
    }
};

错误是：

1:   在start = mid 的时候，没有考虑，if mid == start, 就会有infinite loop

2:   在while loop中，一开始，画蛇添足。加了别的停止条件了。 哎。人生啊