检查矩阵中重复行的高效算法

Question

给定矩阵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.

我能做得比这更好吗？或者,上面的方法有什么缺陷？

Answer 1

你的方法有效,但你的复杂性是错的.

首先,测试元素是否std::map具有复杂性O(log(n) * f),其中n是地图中元素的数量,并且f是比较地图中插入/搜索的任何两个元素所需时间的上限.

在您的情况下,每个字符串都有一个长度m,因此比较地图成本中的任何两个元素O(m).

所以你的方法的总复杂性是:

O(n * log(n) * m)用于n在地图中插入字符串.

但是,您可以将其加速到O(n * m)期望值,这是渐近最优的(因为您必须读取所有数据),使用哈希表而不是地图.这样做的原因是哈希表具有O(1)插入操作的平均复杂度,并且每个输入字符串的哈希函数仅计算一次.

在C++你可以使用unordered_set.