9ms run-time solution using C++


  • 0
    S

    The idea is basically borrowed from DBScan algorithm. Code is shown below:

    class Solution {
    public:
        int get_cluster_equivalent(int c1, map<int, int>&in_map)
        {
    
            map<int, int>::iterator f;
    
            f = in_map.find(c1);
    
            if(f != in_map.end())
            {
                return this->get_cluster_equivalent(f->second, in_map);
            }
            else
            {
                return c1;
            }
        }
    
        int assign_clusters(int c1, int c2, map<int, int>&in_map)
        {
            if(c1 == c2)
                return -1;
    
            int e1 = this->get_cluster_equivalent(c1, in_map);
            int e2 = this->get_cluster_equivalent(c2, in_map);
    
            if(e1 == c1 && e2 == c2)
            {
                in_map.insert(pair<int,int>(c1, c2));
            }
            else if(e1 == c1 && e2 != c1)
            {
                in_map.insert(pair<int, int>(c1, e2));
            }
            else if(e2 == c2 && e1 != c2)
            {
                in_map.insert(pair<int, int>(c2, e1));
            }
            else
            {
                this->assign_clusters(e1, e2, in_map);
            }
    
            return 0;
        }
    
    
        int numIslands(vector<vector<char> > &grid) {
            int cur_islands = 2;
            int ** cluster_grids = (int **)calloc(grid.size(), sizeof(int *));
            int row_num = grid.size();
            if(row_num < 1)
                return 0;
            int col_num = grid[0].size();
            for (int i = 0; i < row_num; i++)
                cluster_grids[i] = (int *) calloc(col_num, sizeof(int));
    
            for(int i = 0; i < row_num; i++)
            {
                for(int j = 0; j < col_num; j++)
                {
                    cluster_grids[i][j] = grid[i][j] - '0';
                }
            }
    
            map<int, int> clusters_map;
    
            for(int i = 0; i < row_num; i++)
            {
                for(int j = 0; j < col_num; j++)
                {
                    int cur = cluster_grids[i][j];
    
                    if(cur > 0)
                    {
                        if(j > 0 && cluster_grids[i][j-1] > 0)
                        {
                            if (cur != 1 && cur != cluster_grids[i][j-1])
                            {
                                this->assign_clusters(cur, cluster_grids[i][j-1], clusters_map);
    
                            }
                            else if (cur != cluster_grids[i][j-1])
                            {
                                cluster_grids[i][j] = cluster_grids[i][j-1];
                                cur = cluster_grids[i][j];
                            }
                            if(i > 0 && cluster_grids[i - 1][j] > 0 && cur != cluster_grids[i - 1][j])
                            {
                                this->assign_clusters(cur, cluster_grids[i - 1][j], clusters_map);
                            }
                        }
                        else if (i > 0 && cluster_grids[i - 1][j] > 0)
                        {
                            if (cur != 1 && cur != cluster_grids[i - 1][j])
                            {
                                this->assign_clusters(cur, cluster_grids[i - 1][j], clusters_map);
                            }
                            else if (cur != cluster_grids[i - 1][j])
                            {
                                cluster_grids[i][j] = cluster_grids[i - 1][j];
                            }
                        }
                        else
                        {
                            cluster_grids[i][j] = cur_islands;
                            cur_islands++;
                        }
                    }
                }
            }
    
            return cur_islands - 2 - clusters_map.size();
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.