LeetCode_73_Set Matrix Zeroes

思路较简单，对出现0的行或者列做好标记就好

我突发奇想，看看 set的查找和一般数组的随机访问差别有多大……

用set实现：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m,n,i,j;
		set<int> row,col;
		m=matrix.size();
		if(m==0)
			return;
		n=matrix[0].size();
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(matrix[i][j]==0)
				{
					row.insert(i);
					col.insert(j);
				}
		if(row.size()==0 && col.size()==0)
			return;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(row.find(i)!=row.end() || col.find(j)!=col.end())
					matrix[i][j]=0;
    }
};

用vector记录：

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m,n,i,j,flag=0;
		m=matrix.size();
		if(m==0)
			return;
		n=matrix[0].size();
		vector<int> row(m),col(n);
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(matrix[i][j]==0)
				{
					row[i]=1;
					col[j]=1;
					flag=1;
				}
		if(flag=0)
			return;
		for(i=0;i<m;i++)
			for(j=0;j<n;j++)
				if(row[i] || col[j])
					matrix[i][j]=0;
    }
};

运行时间对比：

本题只有159个测试用例，就有4ms的差距，看来访问效率还是有点不一样的