lurenaa的博客

😂二分查找

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
class Solution {
public:
    vector<int> findClosestElements(vector<int>& nums, int k, int x) {
        vector<int> vec;
        int lo = 0, 
        hi = nums.size() - 1, m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] < x) {
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        int lol = lo - 1;
        while(lol >= 0 && lo < nums.size() && k) {
            if(abs(nums[lol] - x) > abs(nums[lo] - x)) {
                --k;
                vec.push_back(nums[lo++]);
            } else {
                --k;
                vec.push_back(nums[lol--]);
            }
        }
        while(k && lo < nums.size()) {
            --k;
            vec.push_back(nums[lo++]);
        }
        while(k && lol >= 0) {
            --k;
            vec.push_back(nums[lol--]);
        }
        sort(vec.begin(), vec.end());
        return vec;
    }
};

Accepted

56/56 cases passed (80 ms)

Your runtime beats 66.67 % of cpp submissions

Your memory usage beats 5.13 % of cpp submissions (15 MB)

😷第二次

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
class Solution {
public:
    vector<int> findClosestElements(vector<int>& nums, int k, int x) {
        vector<int> vec;
        int lo = 0, 
        hi = nums.size() - 1, m;
        while(lo < hi) {
            m = lo + (hi - lo) / 2;
            if(nums[m] < x) {
                lo = m + 1;
            } else {
                hi = m;
            }
        }
        int lol = lo - 1;
        while(lol >= 0 && lo < nums.size() && k) {
            if(x - nums[lol] > nums[lo] - x) {
                --k;
                vec.push_back(nums[lo++]);
            } else {
                --k;
                vec.insert(vec.begin(), nums[lol--]);
            }
        }
        while(k && lo < nums.size()) {
            --k;
            vec.push_back(nums[lo++]);
        }
        while(k && lol >= 0) {
            --k;
            vec.insert(vec.begin(), nums[lol--]);
        }
        // sort(vec.begin(), vec.end());
        return vec;
    }
};

Accepted

56/56 cases passed (220 ms)

Your runtime beats 9.55 % of cpp submissions

Your memory usage beats 5.13 % of cpp submissions (15 MB)

🥵最优解

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int lo = 0, hi = arr.size() - k;
    while (lo < hi) {
        int mid = lo + (hi - lo >> 1);
        if (x - arr[mid] > arr[mid + k] - x ) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return vector<int>(arr.begin() + lo, arr.begin() + lo + k);
}

Accepted

56/56 cases passed (76 ms)

Your runtime beats 68.03 % of cpp submissions

Your memory usage beats 8.06 % of cpp submissions (14.4 MB)


 上一页

LeetCode