-3

如何使用可比较的函数而不是使用位置数组按最后一列对 2D 矩阵进行排序？

4 20 15 23 18 9 89 1 8 23 22 14 18 86 17 15 13 18 12 15 90 3 18 8 20 12 5 66

这是我的二维矩阵示例，其中最后一列表示行i = 1 -> n的元素之和。我必须按升序对行进行排序，比较最后一列的元素。

编辑！

第一个代码是这个：

int main()
{
    int x[101][101],y[101],z[101],n,m;
    int i,I,j,l,Mi=1000001,b=0;
    int s=0;

    cin>>n>>m;

    for(i=1;i<=n;i++)
        for(I=1;I<=m;I++)
            cin>>x[i][I];
    for(i=1;i<=n;i++)
    {
        s=0;
        for(I=1;I<=m;I++)
            s=s+x[i][I];
        y[i]=s;
    }
    for(l=1;l<=n;l++)
    {
        Mi=1000001;
        for(j=1;j<=n;j++)
            if(y[j]<Mi)
            {
                Mi=y[j];
                b=j;
            }
        z[l]=b;
        y[b]=1000002;
    }

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            cout<<x[z[i]][j]<<" ";
        cout<<endl;
    }
    return 0;
}

但正如我所说..我使用的位置数组不是最好的，因为它们占用了大量空间，我不希望这样。该数组是一个整数数组。我被卡住了，因为我不知道另一种方法，这就是为什么我想寻求您的帮助。

4

2 回答 2

1

看看这个简单的例子。我建议使用 std::vector 来存储矩阵。对于排序，使用 std::sort 和定义的比较 lambda ( cmp )。

#include <iostream>
using namespace std;

const int C = 5, R = 5;
using row = vector<int>;
using matr = vector<row>;

struct matrix
{
    matr m_matrix;
    matrix(int row, int col)
    {
        m_matrix.resize(row);
        for(auto &a : m_matrix)
            a.resize(col);
    }
    void set(int r, int c, int val)
    {
        m_matrix[r][c] = val;
    }
    void sort()
    {
        auto cmp = [](const row &r1, const row &r2)
        {
            return r1[r1.size() - 1] < r2[r2.size() - 1];
        };
        std::sort(m_matrix.begin(), m_matrix.end(), cmp);
    }
    void print()
    {
        for(auto &a : m_matrix)
        {
            for(auto v : a)
                cout << v << "  ";
            cout << endl;
        }
    }
};


void fill_matrix(matrix &m)
{
    int cntr = 15;
    for(int i = 0;i < C;i++)
    {
        int sum = 0;
        for(int j = 0;j < R - 1;j++)
        {
            int value = 10 + (cntr++) % 20;
            m.set(i, j, value);
            sum += value;
        }
        m.set(i, R - 1, sum);
    }
}


int main(int argc, char* argv[])
{
    matrix m(5, 5);
    fill_matrix(m);    
    m.print();
    cout << endl;
    m.sort();
    m.print();
}

结果：

在此处输入图像描述

于 2018-11-30T14:34:46.300 回答
1

首先 - 使用std::array<T, size>而不是 C 风格的方括号数组 ( T[])。用法：

std::array<std::array<int, 7>, 4> matrix{
        {
                {{4, 20, 15, 23, 18, 9, 89}},
                {{1, 8, 23, 22, 14, 18, 86}},
                {{17, 15, 13, 18, 12, 15, 90}},
                {{3, 18, 8, 20, 12, 5, 66}}
        }
};

虽然括号的数量一开始可能看起来很奇怪，但当您意识到工具的强大功能时，您很快就会忘记它std::array。

其次 - 使用标准算法。你需要：

  • 获取给定行的最后一个元素
  • 获取另一行的最后一个元素
  • 定义一个比较函数，该函数将比较上述元素以有效地用于比较整行
  • 将该函数与标准排序算法一起使用：std::sort

建议的解决方案：

std::sort(matrix.begin(), matrix.end(), [](const auto& first_row,
                                           const auto& second_row) {
    return first_row.back() < second_row.back();
});

我们使用lambda 表达式来定义比较两行的比较器。这就是所有std::sort需要 - 一种比较它排序的范围的两个元素的方法 - 在这种情况下，我们定义如何比较矩阵的两行（常用C++方法是使用小于运算符提供严格的弱排序 - 这就是<为什么用于比较最后一个元素或每一行。如果您希望颠倒顺序，只需使用>。不要使用其中之一<=或>=尽管，因为它们不提供严格的排序）。

于 2018-11-30T14:37:56.180 回答