要成功就做一百题-91

题目名称

矩阵置零

描述

难度属于中等，如下是题目的描述，leetcode 73题。

//给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。 
//
// 示例 1: 
//
// 输入: 
//[
//  [1,1,1],
//  [1,0,1],
//  [1,1,1]
//]
//输出: 
//[
//  [1,0,1],
//  [0,0,0],
//  [1,0,1]
//]

解题思路

这里我也没用其他复杂的东西，就是按照图形化的直观第一印象，找到等于0的位置的坐标并保存，然后从坐标开始，依次上下、左右地开始置为0；这里保存坐标用了个特殊的方式，定义两个数组列表，因为坐标是成对出现的，同时加入，序号一致，在置零的阶段，遍历坐标也比较方便。本来是中等难度的题目，没想到第一提交就通过了，而且耗时1ms超过100%，内存40MB超过80%，如下是详细的代码，这一直接单测。

代码

    @Test
    public void matrixTest() {
        int[][] matrix = new int[][] {{1, 1, 1}, {1, 9, 1}, {1, 2, 1}, {1, 0, 2}};
        setZeroes(matrix);
    }

    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;

        List<Integer> mList = new ArrayList<>();
        List<Integer> nList = new ArrayList<>();
        for (int k = 0; k < m; k++) {
            for (int l = 0; l < n; l++) {
                if (matrix[k][l] == 0) {
                    mList.add(k);
                    nList.add(l);
                }
            }
        }
        for (int i = 0; i < mList.size(); i++) {
            int im = mList.get(i);
            int in = nList.get(i);

            int x = 0;
            int y = 0;
            while (x < m) {
                matrix[x++][in] = 0;
            }
            while (y < n) {
                matrix[im][y++] = 0;
            }
        }
        System.out.println(arrayToString(matrix));
    }

    private String arrayToString(Object[] arr) {
        StringBuilder builder = new StringBuilder("[");
        for (Object o : arr) {
            if (o instanceof int[]) {
                builder.append(Arrays.toString((int[]) o));
            }
        }
        builder.append("]");
        return builder.toString();
    }

总结