怎么今天还是数学题？

54. Spiral Matrix

Analysis

这个题是在 PTA 上做过的题，题意很简单，其实就是按照螺旋顺序输出数组。

Code

两个注意的地方：

当矩阵只有一个元素时，需要特判一下。
当矩阵是 $n × n$ 的方阵时，中间的元素需要特判一下，不然会死循环。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int index = 0, count = m * n, r = 0, c = 0;
        if(count == 1) return matrix[0];
        int U = 0, D = m - 1, L = 0, R = n - 1;
        vector<int> ret(count);
        while(index < count) {
            while(index < count && c < R) ret[index++] = matrix[r][c++];
            while(index < count && r < D) ret[index++] = matrix[r++][c];
            while(index < count && c > L) ret[index++] = matrix[r][c--];
            while(index < count && r > U) ret[index++] = matrix[r--][c];
            r++, c++;
            U++, D--, L++, R--;
            if(index == count - 1) {
                ret[index++] = matrix[r][c];
                break;
            }
        } 
        return ret;
    }
};

973. K Closest Points to Origin

Analysis

找出距离原点最近的 k 个点，有点按照距离排序的味道。

Code

method 1

先排序再说：

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int size = points.size();
        vector<int> dis(size);
        vector<int> indices(size);
        for(int i = 0; i < size; i++) {
            dis[i] = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        }
        iota(indices.begin(), indices.end(), 0);
        sort(indices.begin(), indices.end(), [&](int i, int j) { return dis[i] < dis[j]; });
        vector<vector<int>> ret;
        for(int i = 0; i < k; i++) {
            ret.push_back(points[indices[i]]);
        }
        return ret;
    }
};

好吧，果然是排序啊，从周赛题学来的思路用到了。
仔细想想，重新用数组排序，不如直接拿原数组排序😓：

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), [](auto &a, auto &b) {
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        });
        return {points.begin(), points.begin() + k};
    }
};

记得排序时要引用，不然时间、内存消耗惨不忍睹...
这样排序其实没有上面快，可能是因为计算过程在排序内部的原因。

method 2

这个题还可以从堆的角度来思考。由于 C++ 的 priority queue 默认的是大根堆，可以先将前 k 个元素放入堆内，然后遍历剩余 n - k 个元素。每个元素与堆顶元素比较，如果距离大于堆顶元素，就弹出堆顶元素，并将当前元素入队。这样，遍历结束后，堆内的元素就是需要的结果。

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, int>> q;
        for(int i = 0; i < k; i++) {
            q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
        }
        int size = points.size();
        for(int i = k; i < size; i++) {
            int dis = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if(dis < q.top().first) {
                q.pop();
                q.emplace(dis, i);
            }
        }
        vector<vector<int>> ret;
        while(!q.empty()) {
            ret.push_back(points[q.top().second]);
            q.pop();
        }
        return ret;
    }
};

method 3

按照官方题解的思路，这个题还可以从快排的角度来思考：

class Solution {
    mt19937 gen{random_device{}()};
public:
    void random_select(vector<vector<int>>& points, int left, int right, int k) {
        int pivot_id = uniform_int_distribution<int>{left, right}(gen);
        int pivot = points[pivot_id][0] * points[pivot_id][0] + points[pivot_id][1] * points[pivot_id][1];
        swap(points[right], points[pivot_id]);
        int i = left - 1;
        for(int j = left; j < right; j++) {
            int dis = points[j][0] * points[j][0] + points[j][1] * points[j][1];
            if(dis <= pivot) {
                i++;
                swap(points[i], points[j]);
            }
        }
        i++;
        swap(points[i], points[right]);
        if(k < i - left + 1) random_select(points, left, i - 1, k);
        else if( k > i - left + 1) random_select(points, i + 1, right, k - (i - left + 1));
    }
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        int size = points.size();
        random_select(points, 0, size - 1, k);
        return {points.begin(), points.begin() + k};
    }
};

对目前的自己信息量有点大，先放着了😑。
但是得先记着直接调用库函数的解决方法：

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        nth_element(points.begin(), points.begin() + k - 1, points.end(), [](auto &a, auto &b) {
            return a[0] * a[0] + a[1] * a[1] < b[0] * b[0] + b[1] * b[1];
        });
        return {points.begin(), points.begin() + k};
    }
};

太顶了😂。

Summary

矩阵的题做的有点无聊了，第二个题感觉还可以，有点意思~