01 Matrix

https://leetcode.com/problems/01-matrix/description/

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Thoughts

很直观的一个想法是依次以不为0的点为起点做BFS, 当每个点遇到一个为0的点则把距离记下, 停止搜索并切换到下一个点重复此过程. 后来看到大神的做法, 是把所有为0的点压入queue中, 然后一起开始遍历. 每次把遇到的非INF点设为当前遍历的层数, 并停止继续往下的遍历, 因为对于该点, 现在的层数是最短的. 这么做大大提升了搜索效率, 因此原来的方法会每个1节点都把附近的非0点再遍历一次. 是O(M^2N^2)复杂度, 高了一个数量级.

Code

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int m = matrix.length, n = matrix[0].length;
        Set<int[]> starters = new HashSet<>();
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    matrix[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] pos = queue.poll();
                for (int[] dir : dirs) {
                    int x = pos[0] + dir[0];
                    int y = pos[1] + dir[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] != 0) {
                        if (matrix[x][y] == Integer.MAX_VALUE) {
                            queue.add(new int[]{x, y});
                            matrix[x][y] = level + 1;
                        } 
                    } 
                }
            }
            level++;
        }

        return matrix;
    }
}

Analysis

时间复杂度O(MN). M行N列. 因为每个节点都会最先被离得最近的0标记, 也就是说未来即使有其它点访问到也不会继续遍历, 因此每个节点只会被放入queue一次. 或者说每个点只会被放入queue一次.