給定一個整數矩陣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.
我可以做的比這更好的?或者,上面的方法有什麼缺陷?
我不指望你可以做得比O(mn)更好,因爲在最壞的情況下,每個元素都需要被讀取。 – Matt
@Matt說過的理由是最理想的。只是一個警告,你需要在連接元素時加上一些分隔符。否則「{1,23}」和「{12,3}」將被視爲相同。 – justhalf
@justhalf:謝謝你指出。 –