c++ solution easy to understand O(n)


  • 0
    Q
    class Solution {
    public:
        vector<int> findClosestElements(vector<int>& arr, int k, int x) {
            vector<int> res;
            if(k<=0)
                return res;
            int i = 0;
            while(i+1<arr.size()){
                if(abs(arr[i] - x) >= abs(arr[i+1] - x))
                    i++;
                else
                    break;
            }
            
            int start = i, end = i;
            while(end - start + 1< k){
                if(end + 1 == arr.size()){
                    start = end - k + 1;
                    break;
                }
                if(start -1 < 0){
                    end = k-1;
                    break;
                }
                if(abs(arr[start - 1] - x) <= abs(arr[end+1] - x))
                    start--;
                else
                    end++;
            }
            
            for(int i=start;i<=end;i++)
                res.push_back(arr[i]);
            
            return res;
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.