0

我正在将 python(sage) 程序翻译成 C++ 程序。

我需要编写一个函数来操作矩阵，并且我需要找到矩阵中最大元素的索引。

我想尽可能高效地做到这一点，但到目前为止我想出的唯一一件事似乎效率很低。

我的算法的伪代码是，

  1. 给定一个矩阵，在每一行调用 max_element 函数
  2. 创建一个向量并 push_back 从 max_element 返回的迭代器
  3. 取消对迭代器的引用，再次调用 max_element 函数
  4. 查找列的索引
  5. 查找行的索引

这将非常混乱和缓慢.. 有没有人有更好的算法来完成这项任务？谢谢你。

4

2 回答 2

3

自己编写外循环可能最简单：

if (matrix.size() == 0 || matrix[0].size() == 0) {
    // matrix is empty, handle special case
    throw std::logic_error("empty");
}
int best = matrix[0][0];
size_t rowidx = 0, colidx = 0;
for (auto it = matrix.begin(); it != matrix.end(); ++it) {
    auto maxit = max_element(it->begin(), it->end());
    if (*maxit > best) {
        best = *maxit;
        rowidx = it - matrix.begin();
        colidx = maxit - it->begin();
    }
}

或者，您可以编写一个迭代整个矩阵的迭代器类：

struct MatrixIterator : std::iterator<std::forward_iterator_tag, int> {
    typedef vector<vector<int> > Matrix;
    Matrix &m;
    size_t rowidx, colidx;
    explicit MatrixIterator(Matrix &m, size_t row = 0, size_t col = 0) : m(m), rowidx(row), colidx(col) {};
    int &operator*() { return m[rowidx][colidx]; }
    MatrixIterator &operator++() {
        ++colidx;
        if (colidx == m[rowidx].size()) {
            colidx = 0;
            ++rowidx;
        }
        return *this;
    }
    MatrixIterator operator++(int) {
        MatrixIterator result = *this;
        ++*this;
        return result;
    }
    bool operator==(const MatrixIterator &rhs) {
        return rowidx == rhs.rowidx && colidx == rhs.colidx;
    }
    bool operator!=(const MatrixIterator &rhs) {
        return ! (*this == rhs);
    }
    static MaxtrixIterator end(Matrix &m) {
        return MatrixIterator(m, m.size() - 1, m.back().size());
    }
};

现在你可以这样做：

MatrixIterator result = std::max_element(MatrixIterator(m), MatrixIterator::end(m));
size_t rowidx = result.rowidx, colidx = result.colidx;
于 2013-07-02T17:37:52.667 回答
0

我假设您将数据存储在二维向量中。

#include <vector>
#include <algorithm>
vector<vector<int>> Matrix

你应该能够像这样迭代你的矩阵以获得最大的元素

int MaxValue = 0;
for(int i = 0; i < Matrix.size(); i++) {
    if( *std::max_element(Matrix[i].begin(),Matrix[i].end()) < MaxValue ) continue;
    MaxValue = *std::max_element(Matrix,Matrix+Columns);
}
于 2013-07-02T17:43:17.687 回答