我的任务是计算C++中 2D 数组的每个元素的相应行i和列j中大于元素a ij的元素的数量。我的方法是提取第i 行和第 j列，对它们进行排序并使用计数器变量遍历排序后的数组，直到找到ij元素。
但问题在于为每个此类元素提取整行i和整列j。我知道可以使用 c++ 中的std::copy函数轻松提取该行。
int **adj=new int *[n];
for(r=0;r<m;r++)
for(c=0;c<n;c++)
cin>>adj[r][c];
int buf[n];
std::copy(adj[i], adj[i] + n, buf);
但是如何提取相应的第j列呢？
我可以使用循环结构轻松做到这一点，例如：
int buf[m];
for(r=0;r<m;r++)
buf[r]=adj[r][j];
但这会增加时间复杂度，请记住，数组的每个元素都需要此操作。有什么更好的方法可以做到这一点吗？
如果你决定用C++编写程序，那么
- 停止使用普通的 C 样式数组。没有任何理由使用 C 样式数组。切勿再次使用它们。只需停止此操作即可。
- 停止使用原始指针。现在和永远。不要使用原始指针
- 不要使用新的。从不
- 您要使用的语言C++不支持 VLA(可变长度数组)，首先不要使用 C 样式数组，也根本不要使用 VLA(如
int buf[m]; - 特别是，如果您不了解这些结构的工作原理，请不要使用此类结构
在你的第一排，你正在写
int **adj=new int *[n];
这样，您就可以分配一个指针数组。这些指针未初始化。他们指向记忆中的某个随机位置。
并与
for(r=0;r<m;r++)
for(c=0;c<n;c++)
cin>>adj[r][c];
您正在获取用户输入并将其写入随机内存，有时未被修改，损坏堆并导致崩溃。
跟
int buf[n];
std::copy(adj[i], adj[i] + n, buf);
您将一些随机值复制到 BUB 中。它看起来会起作用。但这只是偶然的。
将来请使用std::vector或std array(如果您在编译时知道维度)。对于二维数组，请使用向量的向量。
请参阅以下示例：
int main()
{
const size_t numberOfRows = 3;
const size_t numberOfColumns = 4;
std::vector<std::vector<int>> a2d(numberOfRows, std::vector<int>(numberOfColumns));
// Fill a2d with data
for (size_t row = 0; row < a2d.size(); ++row) {
for (size_t col = 0; col < a2d.front().size(); ++col) {
std::cin >> a2d[row][col];
}
}
// Get 2nd row
std::vector<int> row(numberOfColumns);
std::copy(a2d[1].begin(), a2d[1].end(), row.begin());
return 0;
}
但是问题在于为每个这样的元素提取整个行 i 和整个列 j。
您尝试实现的算法不需要每次都复制和排序行和列。您可以复制和排序每一行和每一列一次，然后为每个元素重复使用它们。虽然很耗时，但它应该比多次遍历行和列来计算更大的值要快得多。
例如，请参阅以下实现(可在此处测试)。
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
int main()
{
std::vector<std::vector<int>> a {
{3, 5, 1, 2},
{8, 0, -2, 7},
{1, -5, 3, 6},
};
// Make a transposed copy. That's really cache unfriendly
auto a_t = std::vector<std::vector<int>>(a[0].size(), std::vector<int>(a.size()));
for (size_t r = 0; r < a.size(); ++r)
{
for (size_t c = 0; c < a[r].size(); ++c)
{
a_t[c][r] = a[r][c];
}
}
// Sort the rows of a_t (columns of a)
for (auto & row : a_t)
{
std::sort(row.begin(), row.end());
}
auto c = std::vector<std::vector<int>>(a.size(), std::vector<int>(a[0].size()));
for (size_t i = 0; i < c.size(); ++i)
{
// Sort a (copied) row at a time.
auto row_copy(a[i]);
std::sort(row_copy.begin(), row_copy.end());
// The columns have already been copied and sorted,
// now it just takes a couple of binary searches.
for (size_t j = 0; j < c[i].size(); ++j)
{
auto it_r = std::upper_bound(row_copy.cbegin(), row_copy.cend(), a[i][j]);
auto it_c = std::upper_bound(a_t[j].cbegin(), a_t[j].cend(), a[i][j]);
c[i][j] = std::distance(it_r, row_copy.cend())
+ std::distance(it_c, a_t[j].cend());
}
}
for (auto const & row : c)
{
for (auto i : row)
std::cout << std::setw(3) << i;
std::cout << 'n';
}
}