[LeetCode]Sparse Matrix Multiplication

稀疏矩阵相乘的问题，假设A矩阵为m * n，B矩阵为n * k，那么输出矩阵为m * k，并且求每一个元素的实际那复杂度是O(n)，总的时间复杂度就是O(m * n * k)。但是既然题目说了是稀疏矩阵，那么我们可以免去很多不必要的计算。比如，对于A矩阵，我们就可以把其转化为Hashmap of hashmap，只存不为0的数的索引，我们只需要遍历hashmap每一行对应的不为0的元素然后去B中找对应的元素相乘累加到对应的位置即可。假设A中每行不为0的元素平均数量为d，d肯定远小于n，那么时间复杂度为O(m * d * k)，空间复杂度O(m * d), 代码如下：

	class Solution {
	public:
	vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
	int m = A.size(), n = m ? A[0].size() : 0, k = B.size() ? B[0].size() : 0;
	vector<vector<int>> res(m, vector<int>(k, 0));
	unordered_map<int, unordered_map<int, int>> matrix;
	for (int i = 0; i < m; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	if(A[i][j])
	matrix[i][j] = A[i][j];
	}
	}
	for (int i = 0; i < m; ++i)
	{
	for (int j = 0; j < k; ++j)
	{
	auto row = matrix[i];
	for (auto&& cell : row)
	{
	int col = cell.first;
	if (B[col][j])res[i][j] += cell.second * B[col][j];
	}
	}
	}
	return res;
	}
	};

view raw Sparse Matrix Multiplication_1.cpp hosted with ❤ by GitHub

我们还有一种不用额外空间的方法。对于A中的某个元素A[i][j]，其只可能分别和B[j][0->k]的乘积累加到C[i][0->k]中，所以我们只需要在遍历A的每个不为0的元素的时候，不断更新C即可。时间复杂度为O(m * d * k)，常数空间，代码如下：

	class Solution {
	public:
	vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
	int m = A.size(), n = m ? A[0].size() : 0, k = B.size() ? B[0].size() : 0;
	vector<vector<int>> res(m, vector<int>(k, 0));
	for (int i = 0; i < m; ++i)
	{
	for (int j = 0; j < n; ++j)
	{
	if (A[i][j])
	{
	for (int x = 0; x < k; ++x)
	if (B[j][x])res[i][x] += A[i][j] * B[j][x];
	}
	}
	}
	return res;
	}
	};

view raw Sparse Matrix Multiplication_2.cpp hosted with ❤ by GitHub