给定一个整数矩阵 M。检查矩阵中的两行是否相同。给出最佳方法。
Example:
[{1, 2, 3},
{3, 4, 5},
{1, 2, 3}]
在上面的矩阵中，第 1 行和第 3 行是相同的。
可能的解决方案：
Given a matrix, we can convert each row in a string (example using to_string()
method of C++ and concatenating each element in a row to a string). We do this
for every row of the matrix, and insert it in a table that is something like
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time
for an mxn matrix.
我能做得比这更好吗？或者，上述方法有什么缺陷？
您的方法有效，但您对它的复杂性有误。
首先，测试一个元素是否在 astd::map中具有复杂性O(log(n) * f)，其中n是地图中元素的数量，并且f是比较地图中插入/搜索的任何两个元素所需时间的上限。
在您的情况下，每个字符串都有一个 length m，因此比较地图中的任何两个元素 cost O(m)。
所以你的方法的总复杂度是：
O(n * log(n) * m)用于在地图中插入n字符串。
但是，您可以使用哈希表而不是映射将其加速到O(n * m)预期的速度，这是渐近最优的（因为您必须读取所有数据）。这样做的原因是哈希表O(1)对于插入操作具有平均复杂性，并且每个输入字符串的哈希函数只计算一次。
在C++你可以使用unordered_set。
根据矩阵的大小，将所有内容转换为字符串似乎非常浪费时间和空间。
为什么不为每一行计算一个可能的唯一哈希。例如，您可以计算所有条目的按位或，然后将该哈希与行的索引一起保存在多映射中。当您浏览每一行时，您计算它的哈希值，然后检查该哈希值是否已经存在。如果是这样，请将您的行与具有相同哈希的其他行进行比较，以查看它们是否相等。
这没有更好的 Big-O 复杂性，但几乎可以肯定它具有更小的常数并使用更少的空间。