6ms C++ quick partition solution without sort


  • 0
    M
    
    class Solution {
    public:
        int minTotalDistance(vector<vector<int>>& grid) {
            // min sum [abs(p2x - p1x) + abs(p2y - p1y)] 
            // = min sum (abs(p2x - p1x)) + min sum (abs(p2y - p1y)
            // geometric median of 1-D line is the median
            int m = grid.size();
            if (m == 0) return 0;
            int n = grid[0].size();
            if (n == 0) return 0;
            vector<int> xgrid;
            vector<int> ygrid;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        xgrid.push_back(i);
                        ygrid.push_back(j);
                    }
                }
            }
            nth_element(xgrid.begin(), xgrid.begin() + xgrid.size()/2, xgrid.end());
            nth_element(ygrid.begin(), ygrid.begin() + ygrid.size()/2, ygrid.end());
            int xmid = xgrid[xgrid.size() / 2];
            int ymid = ygrid[ygrid.size() / 2];
            int dist = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1)
                        dist += abs(xmid - i) + abs(ymid - j);
                }
            }
            return dist;
        }
    };
    
    

Log in to reply
 

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