C++ Solution using hashmap


  • 0
    Y
    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            int ans = 0;
            if(grid.size() == 0)
                return ans;
            int n = grid.size(), m = grid[0].size();
            for(int i = 0; i < n; ++ i){
                for(int j = 0; j < m; ++ j){
                    if(grid[i][j]){
                        if(rowcnt.find(i) == rowcnt.end())
                            rowcnt[i] = 1;
                        else
                            ++ rowcnt[i];
                        if(colcnt.find(j) == colcnt.end())
                            colcnt[j] = 1;
                        else
                            ++ colcnt[j];
                    }
                }
            }
            int rans = INT_MAX, cans = INT_MAX;
            for(int i = 0; i < n; ++ i){
                unordered_map<int,int>::iterator it = rowcnt.begin();
                int tmpans = 0;
                for(; it != rowcnt.end(); ++ it){
                    tmpans += it->second*abs(it->first - i);
                }
                rans = min(rans, tmpans);
            }
            for(int i = 0; i < m; ++ i){
                unordered_map<int,int>::iterator it = colcnt.begin();
                int tmpans = 0;
                for(; it != colcnt.end(); ++ it){
                    tmpans += it->second*abs(it->first - i);
                }
                cans = min(cans, tmpans);
            }
            ans = rans + cans;
            return ans;
        }
    private:
    unordered_map<int,int> rowcnt, colcnt;
    };

Log in to reply
 

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