Cracking the coding interview--Q1.7

题目

原文：

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

译文：

写一个函数处理一个MxN的矩阵，如果矩阵中某个元素为0，那么把它所在的行和列都置为0.

解答

简单题。遍历一次矩阵，当遇到元素等于0时，记录下这个元素对应的行和列。 可以开一个行数组row和列数组col，当元素a[i][j]等于0时， 就把row[i]和col[j]置为true。第二次遍历矩阵时，当某个元素对应的行row[i] 或列col[j]被设置为true，说明该元素在需要被置0的行或列上，因此将它置0。

代码如下：

package cha1;

import java.util.ArrayList;
import java.util.List;

public class A007 {
    
    static class Pair {
        int x;
        int y;
    }
    
    public static void fun(int[][] M, int n) {
        List<Pair> pairs = new ArrayList<A007.Pair>();
        for (int i=0; i<n; i++)
            for (int j=0; j<n; j++)
                if (M[i][j] == 0){
                    Pair p = new Pair();
                    p.x = i;
                    p.y =j;
                    pairs.add(p);
                }
        for (Pair p : pairs)
            doit(M, n, p.x, p.y);
    }
    
    private static void doit(int[][] M, int n, int i, int j) {
        for (int k=0; k<n; k++)
            M[i][k] = 0;
        for (int k=0; k<n; k++)
            M[k][j] = 0;
    }
    
    public static int[][] strToM(String str, int n) {
        String[] ss = str.split(" ");
        System.out.println(ss.length);
        int[][] M = new int[n][n];
        int k = 0;
        for (int i=0; i<n; i++){
            for (int j=0; j<n; j++) {
                M[i][j] = Integer.parseInt(ss[k]);
                k++;
            }
        }
        return M;
    }
    
    public static void main(String[] args) {
        String mstr = "1 0 3 4 5 6 7 8 9 10 11 12 13 14 15 16";
        int n= 4;
        int[][] M = strToM(mstr, n);
        fun(M, n);
        for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++)
                System.out.print(M[i][j] + " ");
            System.out.println();
        }
    }
}