问答

当前位置

573. Build Post Office II

  • Ta: 刘钟泽

请问助教老师,

这道题两种方法:
1)对于每一个空地,求reach了所有的房子的最小值
2)对于每一个房子,update global dist 找到最小的被所有房子visit过的空地。

时间复杂度如何分析? 假设矩阵式NM
我觉得一个是O(空地数
NM), 一个是O(房子数N*M) 假设所有的点都是空地,有worst case

另外请问为什么的的这段代码MLE了?

public class Solution {
    /**
     * @param grid: a 2D grid
     * @return: An integer
     */

    int[][] dirs = new int[][]{{0,1},{-1,0},{1,0},{0,-1}};
    public int shortestDistance(int[][] grid) {
        // write your code here
        if(grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0){
            return 0;
        }

        int houseCount = 0;
        int row = grid.length;
        int col = grid[0].length;
        int res = Integer.MAX_VALUE;

        HashSet<Integer> visited = new HashSet<Integer>();
        Queue<Integer> queue = new LinkedList<Integer>();

        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(grid[i][j] == 0){
                    res = Math.min(res, bfs(grid, i, j, queue, visited));
                    queue.clear();
                    visited.clear();
                }
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;

    }

    private int bfs(int[][] grid, int i, int j, Queue<Integer> queue, HashSet<Integer> visited){

        int row = grid.length;
        int col = grid[0].length;
        int okey = getInt(i, j, col);
        queue.offer(okey);

        visited.add(okey);
        int curDist = -1;
        int sum = 0;
        while(!queue.isEmpty()){
            curDist++;
            int size = queue.size();
            for(int ii = 0; ii < size; ii++){
                Integer cur = queue.poll();
                //update 
                int[] cxy = getIntArray(cur, col);
                int cx = cxy[0];
                int cy = cxy[1];
                if(grid[cx][cy] == 1){
                    sum += curDist;
                    continue;
                }

                //expand 0
                for(int[] dir : dirs){
                    int nx = cx + dir[0];
                    int ny = cy + dir[1];
                    int nkey = getInt(nx, ny, col);

                    //only is 0, because can pass 0 only
                    if(nx >= 0 && nx < row && ny >= 0 && ny < col && !visited.contains(nkey) && grid[nx][ny] != 2){
                        queue.offer(nkey);
                        visited.add(nkey);
                    }
                }
            }
        }

        for(int ii = 0; ii < grid.length; ii++){
            for(int jj = 0; jj < grid[0].length; jj++){
                int key = getInt(ii, jj, col);
                if(grid[ii][jj] == 1 && !visited.contains(key)){

                    return Integer.MAX_VALUE;
                }
            }
        }

        return sum;
    }

    private int getInt(int i, int j, int colSize){
        return i*colSize + j;
    }

    private int[] getIntArray(int num, int colSize){

        return new int[]{num/colSize, num%colSize};
    }
}

1 个回复

2019-02-19 刘钟泽

你的时间复杂度分析是对的。一般来说房子数会比空地数目少,所以选择方法2会比较好。
这道题的空间卡的比较严,你可以使用boolean[] visited = new boolean[row*col]来代替hashmap,这样可以节省一些空间。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1