題目 1693:
數(shù)據結構-稀疏矩陣快速轉置
時間限制: 2s
內存限制: 96MB 提交: 282 解決: 146
題目描述
稀疏矩陣的存儲不宜用二維數(shù)組存儲每個元素，那樣的話會浪費很多的存儲空間。所以可以使用一個一維數(shù)組存儲其中的非零元素。這個一維數(shù)組的元素類型是一個三元組，由非零元素在該稀疏矩陣中的位置（行號和列號對）以及該元組的值構成。
而矩陣轉置就是將矩陣行和列上的元素對換。參考算法5.1中的具體做法，令mu和nu分別代表稀疏矩陣的行數(shù)和列數(shù)，不難發(fā)現(xiàn)其時間復雜度為O(mu×nu)。而當非零元的個數(shù)tu與mu×nu同數(shù)量級時，算法5.1的時間復雜度將上升至O(mu×nu2)。因此，需要采用快速的稀疏矩陣轉置算法。
現(xiàn)在就請你實現(xiàn)一個快速的對稀疏矩陣進行轉置的算法。以下是稀疏矩陣快速轉置的算法描述：
輸入格式
輸入的第一行是兩個整數(shù)r和c（r<200, c<200, r*c <= 12500），分別表示一個包含很多0的稀疏矩陣的行數(shù)和列數(shù)。接下來有r行，每行有c個整數(shù)，用空格隔開，表示這個稀疏矩陣的各個元素。
輸出格式
輸出為讀入的稀疏矩陣的轉置矩陣。輸出共有c行，每行有r個整數(shù)，每個整數(shù)后輸出一個空格。請注意行尾輸出換行。
樣例輸入
6 7 0 12 9 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 0 0 14 0 0 0 24 0 0 0 0 0 18 0 0 0 0 0 15 0 0 -7 0 0 0
樣例輸出
0 0 -3 0 0 15 12 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0