Given a sparse matrix, implement below two methods: void set(int row, int col, int val) //Update value at given row and col; int sum(int row, int col) //Get sum from top left corner to given row, col sub-matrix.
給出一個(gè)稀疏矩陣，要求實(shí)現(xiàn)兩個(gè)方法：第一個(gè)是更新指定行列的元素值，第二個(gè)是給出行列值，求從左上到該坐標(biāo)的子矩陣的元素值之和。

1. 詢問(wèn)

假如不明白稀疏矩陣是什么意思，應(yīng)該要問(wèn)清楚。

2. 分析

常規(guī)方法

一個(gè)非常自然的想法就是存儲(chǔ)[row, col, val]這樣的元素。那么空間復(fù)雜度上是O(n)。
假如用這種存儲(chǔ)方法，set函數(shù)就必須遍歷所有元素來(lái)找到對(duì)應(yīng)的row和col值，復(fù)雜度O(n)；而sum函數(shù)，也需要遍歷所有元素把范圍內(nèi)的挑出來(lái)相加，復(fù)雜度還是O(n)。

如何改進(jìn)

在上面這種解法中，瓶頸主要是在查找?？梢钥紤]利用哈希表來(lái)降低查找的時(shí)間復(fù)雜度。
但是，這道題里面行和列兩者是并列的，如何映射？

解法1

一種思路是把行和列映射成為一個(gè)值，而且不同的行列值這個(gè)值必須不同。例如，我們知道m(xù)xn的矩陣?yán)锩嬗衜*n個(gè)元素，因此可以用序號(hào)0~m*n-1來(lái)唯一確定這些元素，也就是說(shuō):
hash(row, col) = row*n + col，同樣從hash到row和col: row = hash(row, col)//n, col = hash(row, col)%n。
建立如上映射關(guān)系之后，set方法就可以直接查找，時(shí)間復(fù)雜度降為O(1)；而對(duì)于sum方法，還是要遍歷所有元素，O(n)。此外，因?yàn)槭褂昧斯１?，空間復(fù)雜度為O(n)。

解法2

此外，因?yàn)橛衦ow和col兩個(gè)查詢參數(shù)，可以用兩層哈希表。第一層是row為key，value則是下一層的哈希表；第二層是col為key，然后給的元素值作為value。也就是{row:{col:val}}。
該方法復(fù)雜度和方法1還是一樣。

拓展

上面兩種方法，set函數(shù)都已經(jīng)達(dá)到了理論最優(yōu)，但是sum函數(shù)和最直接的解法相比較也沒(méi)有任何改進(jìn)?？刹豢梢蕴岣遱um函數(shù)的復(fù)雜度呢？
其實(shí)如果是普通的矩陣，可以用二維的Fenwick Tree來(lái)實(shí)現(xiàn)，查詢復(fù)雜度O(logm*logn)，不過(guò)代碼比較難寫，還需要構(gòu)造時(shí)間O(m*n)和更新數(shù)據(jù)O(logm*logn)，對(duì)于稀疏矩陣而言，并不算太合適。

3. 代碼

class Solution:
    def __init__(self, m, n):
        self.m, self.n, self.d = m, n, {}

    def set(self, row, col, val):
        h = (row - 1) * self.n + col
        self.d[h] = val

    def sum(self, row, col):
        s = 0
        for key in self.d.keys():
            r, c = key // self.n, key % self.n
            if r <= row and c <= col:
                s += self.d[key]
        return s

4. 總結(jié)

難度Easy，主要是考察哈希表的使用。