CC150 1.7把矩阵元素为0的行和列清空

1. 
   
2. 
   
3. 
   
4. public class Q1_7{
   
5. 
   
6. public static void SetZero( int[][] matrix){
   
7. 
   
8. boolean [] row= new boolean[ matrix. length ];  //二维矩阵的长度指行数，并且和字符串的长度method不一样，没有（）
   
9. 
   
10. boolean [] column = new boolean[ matrix[0]. length]; //列数
    
11. 
    
12. for (int i =0;i <matrix .length ;i ++){
    
13. 
    
14. for (int j =0;j <matrix [0].length ;j ++){
    
15. 
    
16. if (matrix [i ][j ]==0){
    
17. row [i ]= true;
    
18. column [j ]= true;
    
19. }
    
20. 
    
21. 
    
22. }
    
23. 
    
24. 
    
25. 
    
26. }
    
27. 
    
28. 
    
29. for (int i =0;i <matrix .length ;i ++){
    
30. 
    
31. for (int j =0;j <matrix [0].length ;j ++){
    
32. if (row [i ]||column [j ]){
    
33. 
    
34. matrix [i ][j ]=0;
    
35. 
    
36. }
    
37. 
    
38. 
    
39. }
    
40. 
    
41. }
    
42. 
    
43. 
    
44. }
    
45. 
    
46. 
    
47. public static void main(String[] args){
    
48. 
    
49.         int [][] matrix = new int[][]{
    
50.                         {1,2,3,4,},
    
51.                         {5,6,7,8,},
    
52.                         {9,1,2,4},
    
53.                         {2,0,4,9}
    
54.                      };
    
55. 
    
56. 
    
57. 
    
58. SetZero( matrix);
    
59. for (int i =0;i <4;i ++){
    
60. for (int j =0;j <4;j ++){
    
61. 
    
62. System. out.print( matrix[ i][ j]);
    
63. 
    
64. 
    
65. }
    
66. 
    
67. System. out.println();
    
68. 
    
69. }
    
70. 
    
71. }
    
72. 
    
73. 
    
74. }
    

复制代码

1）原方法是新建一个M*N的矩阵，所以空间复杂度为O（M*N）=N的平方,第二种开两个数组所以为O（M+N）=O（1），对吗？
关闭
2）时间复杂度？

空间：O(M+N)时间：找0的时候扫描一遍原数组O(MN)，设0的时候再扫描一遍原数组O(MN)，所以还是O(MN)

空间O(1)
时间O(MN)
设flag1为第0行是否有0，若有，设为1，若无，设为0
设flag2为第0列是否有0，若有，设为1，若无，设为0
从第一行第一列开始遍历矩阵，若找到0，假设在第m行第n列，则将第0列第m行设为0，将第0行第n列设为0
从第一列开始遍历第0行，将0所在位置的列全部置为0
从第一行开始遍历第0列，将0所在位置的行全部置为0
若flag1为1，则将第0行全部置为0
若flag2为1，则将第0列全部置为0

1. class Solution {
   
2. public:
   
3.         void setZeroes(vector<vector<int>> &matrix) {
   
4.                 int m = matrix.size();
   
5.                 int n = matrix[0].size();
   
6.                 int flag1 = 0;
   
7.                 int flag2 = 0;
   
8.                 for (int j = 0; j < n; j++){
   
9.                         if (matrix.at(0)[j] == 0){
   
10.                                 flag1 = 1;
    
11.                         }
    
12.                 }
    
13.                 for (int i = 0; i < m; i++){
    
14.                         if (matrix.at(i)[0] == 0){
    
15.                                 flag2 = 1;
    
16.                         }
    
17.                 }
    
18.                 for (int i = 1; i < m; i++){
    
19.                         for (int j = 1; j < n; j++){
    
20.                                 if (matrix.at(i)[j] == 0){
    
21.                                         matrix.at(0)[j] = 0;
    
22.                                         matrix.at(i)[0] = 0;
    
23.                                 }
    
24.                         }
    
25.                 }
    
26.                 for (int i = 1; i < m; i++){
    
27.                         if (matrix.at(i)[0] == 0){
    
28.                                 for (int j = 1; j < n; j++){
    
29.                                         matrix.at(i)[j] = 0;
    
30.                                 }
    
31.                         }
    
32.                 }
    
33.                 for (int j = 1; j < n; j++){
    
34.                         if (matrix.at(0)[j] == 0){
    
35.                                 for (int i = 1; i < m; i++){
    
36.                                         matrix.at(i)[j] = 0;
    
37.                                 }
    
38.                         }
    
39.                 }
    
40.                 if (flag1 == 1){
    
41.                         for (int j = 0; j < n; j++){
    
42.                                 matrix.at(0)[j] = 0;
    
43.                         }
    
44.                 }
    
45.                 if (flag2 == 1){
    
46.                         for (int i = 0; i < m; i++){
    
47.                                 matrix.at(i)[0] = 0;
    
48.                         }
    
49.                 }
    
50.         }
    
51. };

复制代码

O(M+N)谁跟你说等于O(1)的。。

jxzhuge12 发表于 2014-8-28 19:07
O(M+N)谁跟你说等于O(1)的。。

俺猜的，O（M+N）=O（N）是么？

TonyJang 发表于 2014-8-28 21:26
俺猜的，O（M+N）=O（N）是么？

恩，，对的，，，

jxzhuge12 发表于 2014-8-28 21:28
恩，，对的，，，

soga，谢谢大牛指导，你的solution比较牛啊

TonyJang 发表于 2014-8-28 21:38
soga，谢谢大牛指导，你的solution比较牛啊

没有啦，也是想了很久才想出来的