c++ - 如何对二维矩阵的行进行排序？

Question

这是我的代码

cin >> n;

    vector<vector<int>> A(n, vector<int>(n));

    for (auto &row : A)
        for (auto &el : row)
            cin >> el;

    for (auto row : A)
        sort(row.begin(), row.end());

    for (auto row : A)
    {
        for (auto el : row)
            cout << el << " ";
        cout << "\n";
    }

例如，如果输入是:

3 ///3 by 3 matrix
1 2 3
2 1 3
3 2 1

输出应为:

1 2 3 
1 2 3
1 2 3

我的代码给了我相同的输入，但我不知道如何解决。

Answer 1

只是在调用std::sort时使用引用而不是副本进行迭代。同样，在打印时最好使用引用，因为复制每一行都会导致O(n)的损失，其中n是该行中元素的数量。

这是代码:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std; // this is not a good practice.

int main() {
    int n; 
    cin >> n;
    vector<vector<int>> A(n, vector<int>(n));
    for (auto &row : A)
        for (auto &el : row)
            cin >> el;
    for (auto &row : A) //change this line
        sort(row.begin(), row.end());
    for (auto &row : A)
    {
        for (auto &el : row)
            cout << el << " ";
        cout << "\n";
    }
    return 0;
}

询问者要求我提供代码以按列对矩阵进行排序。这是代码:

#include <iostream>
#include <algorithm>
#include <vector>

void input_matrix(auto &x) {
    for (auto &i : x)
        for (auto &j : i)
            std::cin >> j;
}

void output_matrix(auto &x) {
    for (auto &i : x) {
        for (auto &j : i)
            std::cout << j << " ";
        std::cout << std::endl;
    }
}

void transpose_matrix(auto &x) {
    size_t n = x.size();
    for (size_t i = 0; i < n; i++)
        for (size_t j = i + 1; j < n; j++)
            std::swap(x[i][j], x[j][i]);
}

void sort_matrix_by_row(auto &x) {
    for (auto &i : x)
        std::sort(i.begin(), i.end());
}

void sort_matrix_by_col(auto &x) {
    transpose_matrix(x);
    sort_matrix_by_row(x);
    transpose_matrix(x);
} 

int main() {
    int n;
    std::cin >> n;
    std::vector<std::vector<int>> A(n, std::vector<int>(n));
    input_matrix(A);
    sort_matrix_by_col(A);
    output_matrix(A);
    return 0;
}