leetcode/KClosest.cpp at master · ankurmoh/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
         int i=0,n=arr.size(),left=0,right=n-1;
         if(k>=n)
             return arr;
         vector<int>res;
        while(i<n)
        {
            int mid = i + (n-i)/2;
            if(arr[mid]<x)
                i=mid+1;
            else
                n=mid;
        }
        // while(left<=right)
        // {
        //     if(abs(arr[left]-x)>abs(arr[right]-x))
        //         left++;
        //     else
        //         right--;
        //     if(right-left+1 == k)
        //         break;
        // }
        // for(i=left;i<=right;i++)
        //     res.push_back(arr[i]);
        // return res;

        right=i;
        left = right-1;
        n = arr.size();
        while((left>=0) || (right<n))
        {
            if(left<0)
            {

                right++;
            }
            else if(right==n)
            {

                left--;
            }
            else if(abs(arr[left]-x)<=abs(arr[right]-x))
            {

                left--;
            }
            else
            {

                right++;
            }
            k--;
            if(k == 0)
                break;

        }
        for(i=left+1;i<right;i++)
            res.push_back(arr[i]);
        return res;
    }
};