Mind palace

some thoughts

0%

973. K Closest Points to Origin

Posted on Edited on In Disqus:
Symbols count in article: 3k Reading time ≈ 3 mins.

quickselection
O(n) time on average O(1) space

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
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        srand(time(NULL));
        int n = points.size(), l = 0, r = n - 1;
        while (l <= r) {
            int k = partition(points, l, r);
            if (k == K - 1) break;
            if (k < K - 1) {
                l = k + 1;
            } else {
                r = k - 1;
            }
        }
        return vector<vector<int>>(begin(points), begin(points) + K);
    }

    int partition(vector<vector<int>>& p, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(p[l], p[v[rand() % 3]]);
        int j = l + 1;
        for (int i = j; i <= r; ++i) {
            if (lt(p[i], p[l])) {
                swap(p[i], p[j++]);
            }
        }
        swap(p[--j], p[l]);
        return j;
    }

    bool lt(const vector<int> &a, const vector<int> &b) {
        return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
    }
};
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
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        srand(time(NULL));
        int n = points.size(), l = 0, r = n - 1;
        while (l <= r) {
            int k = partition(points, l, r);
            if (k == K - 1) break;
            if (k < K - 1) {
                l = k + 1;
            } else {
                r = k - 1;
            }
        }
        return vector<vector<int>>(begin(points), begin(points) + K);
    }

    int partition(vector<vector<int>>& p, int l, int r) {
        vector<int> v{l, l + (r - l) / 2, r};
        swap(p[l], p[v[rand() % 3]]);
        auto pivot = p[l];
        while (l < r) {
            while (l < r && !lt(p[r], pivot)) --r;
            p[l] = p[r];
            while (l < r && lt(p[l], pivot)) ++l;
            p[r] = p[l];
        }
        p[l] = pivot;
        return l;
    }

    bool lt(const vector<int> &a, const vector<int> &b) {
        return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
    }
};

O(nlogK) time O(K) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        int n = points.size();
        using vi = vector<int>;
        auto less = [](const vi &a, const vi &b){return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];};
        priority_queue<vi, vector<vi>, decltype(less)> q(less);
        for (const auto &p : points) {
            q.push(p);
            if (q.size() > K) {
                q.pop();
            }
        }
        vector<vi> res;
        while (!q.empty()) {
            res.push_back(q.top());
            q.pop();
        }
        return res;
    }
};

O(nlog(n-K)) time O(n-K) space

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        int n = points.size();
        using vi = vector<int>;
        auto greater = [](const vi &p1, const vi &p2) {return p1[0] * p1[0] + p1[1] * p1[1] > p2[0] * p2[0] + p2[1] * p2[1];};
        priority_queue<vi, vector<vi>, decltype(greater)> q(greater);
        vector<vector<int>> res;
        for (const auto &p : points) {
            if (q.size() < n - K) {
                q.push(p);
            } else if (greater(p, q.top())) {
                res.push_back(q.top());
                q.pop();
                q.push(p);
            } else {
                res.push_back(p);
            }
        }
        return res;
    }
};