2013-10-17 80 views
6

給定一個整數矩陣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. 

我可以做的比這更好的?或者,上面的方法有什麼缺陷?

+1

我不指望你可以做得比O(mn)更好,因爲在最壞的情況下,每個元素都需要被讀取。 – Matt

+1

@Matt說過的理由是最理想的。只是一個警告,你需要在連接元素時加上一些分隔符。否則「{1,23}」和「{12,3}」將被視爲相同。 – justhalf

+0

@justhalf:謝謝你指出。 –

回答

6

你的方法有效,但你錯了它的複雜性。

首先,測試如果一個元件處於std::map具有複雜O(log(n) * f),其中n是在地圖元素的數量和f是的上界需要比較/插入的任何兩個元素在地圖搜索的時間。

就你而言,每個字符串的長度爲m,因此比較地圖中的任何兩個元素的成本爲O(m)

所以你的方法總的複雜性:

O(n * log(n) * m)用於插入地圖n字符串。

但是,您可以使用哈希表而非地圖來加速達到期望值的O(n * m),因爲這是漸近最優的(因爲您必須讀取所有數據)。原因是哈希表的插入操作的平均複雜度爲O(1),並且每個輸入字符串的哈希函數只計算一次。您可以使用unordered_set

0

根據矩陣的大小,將所有內容轉換爲字符串看起來像是一個相當大的時間和空間浪費。

爲什麼不計算每行可能的唯一散列值。例如,您可以計算所有條目的按位或,然後將該散列和行的索引一起保存到多映射中。當你遍歷每一行時,你計算它的散列值,然後檢查是否已經存在該散列值。如果是這樣,請將您的行與具有相同散列的其他行進行比較,以查看它們是否相等。

這沒有更好的Big-O複雜性,但它幾乎可以肯定具有更小的常量並且佔用更少的空間。