Cracking The Coding Interview 1.7

//Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

//

//这题原答案就是要两个buffer来记录出现0的位置。不知道有没可以不用buffer的方法。

#include <iostream>

using namespace std;

void setZero(int **matrix, int m, int n)

{

	int *hang = new int[n];

	int *lie = new int[m];

	for (int i = 0; i< m; i++)

	{

		for (int j=0; j <n;j++)

		{

			if (matrix[i][j] == 0)

			{

				hang[j] = 1;

				lie[i] = 1;

			}

		}

	}

	for (int i = 0; i<m; i++)

	{

		for (int j = 0; j<n; j++)

		{

			if (hang[j] ==1 || lie[i] ==1)

			{

				matrix[i][j]=0;

			}

		}

	}

}

void display(int **matrix, int size, int n)

{

	for (int k = 0; k<size; k++)

		for (int t = 0; t<n; t++)

		{

			cout<<matrix[k][t]<<"  ";

			if (t==n-1)

			{

				cout<<endl;

			}

		}

}

int main()

{

	int m = 4,n = 5;

	int **p = new int *[m];

	for (int i=0;i<m;i++)

	{

		p[i] = new int[n];

	}

	for (int i =0;i<m;i++)

	{

		for (int j=0;j<n;j++)

		{

			p[i][j] = 2*i+j;

		}

	}

	p[2][3] =0;

	display(p,m,n);

	cout<<endl;

	setZero(p,m,n);

	display(p,m,n);

	return 0;

}
巴特西

Cracking The Coding Interview 1.7

最新文章

热门文章
