时间戳

首页 > 解决方案 > 相同方法的两个相同实现，为什么一个比另一个快得多？

c++ - 相同方法的两个相同实现，为什么一个比另一个快得多？

问题描述

我正在尝试解决这个问题。我的解决方案几乎与最快的解决方案相同。但是对于一个测试用例，我超过了时间限制，而另一个（最快的）没有。有人可以为我解释为什么我的代码这么慢吗？这是我的代码：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int M = grid.size();
        if(M == 0) return 0;
        int N = grid[0].size();
        if(N == 0) return 0;
        int flag = 2;
        int count = 0;
        for(int i = 0; i < M; ++i){
            for(int j = 0; j < N; ++j){
                if(grid[i][j] == '1'){
                    //breadth-first search from here
                    flag++;
                    count++;
                    queue<pair<int, int>> nodes;
                    grid[i][j] = flag;
                    nodes.push({i,j});
                    while(!nodes.empty()){
                        auto node = nodes.front();
                        nodes.pop();
                        if(node.first > 0 && grid[node.first-1][node.second] == '1'){
                            grid[node.first-1][node.second] = flag;
                            nodes.push(make_pair(node.first-1, node.second));
                        }
                        if(node.first < M-1 && grid[node.first+1][node.second] == '1'){
                            grid[node.first+1][node.second] = flag;
                            nodes.push(make_pair(node.first+1, node.second));
                        }
                        if(node.second > 0 && grid[node.first][node.second-1] == '1'){
                            grid[node.first][node.second-1] = flag;
                            nodes.push(make_pair(node.first, node.second-1));
                        }
                        if(node.second < N-1 && grid[node.first][node.second + 1] == '1'){
                            grid[node.first][node.second+1] = flag;
                            nodes.push(make_pair(node.first, node.second+1));
                        }                        
                    }
                }
            }
        }
        return count;
    }
};

这是最快的解决方案。作者非常聪明地使用了数组偏移量，我认为这是他的代码和我的代码之间的唯一区别。但我认为它不会加快代码速度。

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size(), n = m ? grid[0].size() : 0, islands = 0, offsets[] = {0, 1, 0, -1, 0};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    grid[i][j] = '0';
                    queue<pair<int, int>> todo;
                    todo.push({i, j});
                    while (!todo.empty()) {
                        pair<int, int> p = todo.front();
                        todo.pop();
                        for (int k = 0; k < 4; k++) {
                            int r = p.first + offsets[k], c = p.second + offsets[k + 1];
                            if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == '1') {
                                grid[r][c] = '0';
                                todo.push({r, c});
                            }
                        }
                    }
                }
            }
        }
        return islands;
    }
};

标签： c++arraysbreadth-first-search

解决方案

The problem here is that you are overwriting the islands on grid with the value of flag. When the value of flag gets equal to '1', then your code enters an infinite cycle because you are asking for cell with '1' for detecting islands.

With this extra line change on your code I got accepted on the problem.

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int M = grid.size();
        if(M == 0) return 0;
        int N = grid[0].size();
        if(N == 0) return 0;
        int flag = 2;
        int count = 0;
        for(int i = 0; i < M; ++i){
            for(int j = 0; j < N; ++j){
                if(grid[i][j] == '1'){
                    //breadth-first search from here
                    flag++;
                    if (flag == '1') flag++;              /////THIS LINE HERE
                    count++;
                    queue<pair<int, int>> nodes;
                    grid[i][j] = flag;
                    nodes.push({i,j});
                    while(!nodes.empty()){
                        auto node = nodes.front();
                        nodes.pop();
                        if(node.first > 0 && grid[node.first-1][node.second] == '1'){
                            grid[node.first-1][node.second] = flag;
                            nodes.push(make_pair(node.first-1, node.second));
                        }
                        if(node.first < M-1 && grid[node.first+1][node.second] == '1'){
                            grid[node.first+1][node.second] = flag;
                            nodes.push(make_pair(node.first+1, node.second));
                        }
                        if(node.second > 0 && grid[node.first][node.second-1] == '1'){
                            grid[node.first][node.second-1] = flag;
                            nodes.push(make_pair(node.first, node.second-1));
                        }
                        if(node.second < N-1 && grid[node.first][node.second + 1] == '1'){
                            grid[node.first][node.second+1] = flag;
                            nodes.push(make_pair(node.first, node.second+1));
                        }                        
                    }
                }
            }
        }
        return count;
    }
};

Note: This code was only for ilustrate the error, that doesn't mean that is an elegant solution for the bug.

推荐阅读