12-13 lines C++


  • 4

    Treat the two dimensions x and y separately, first collecting the k coordinates of the dimension and then using them to update the total travel distance.


    Solution 1 ... nth_element ... 12 ms, O(mn) average

    Find the median coordinate and sum the distances to the median.

    int minTotalDistance2(vector<vector<int>>& grid) {
        int total = 0, X = grid.size(), Y = grid[0].size();
        for (int dim=0; dim<2; ++dim) {
            int c[X*Y], k = 0;
            for (int x=0; x<X; ++x)
                for (int y=0; y<Y; ++y)
                    if (grid[x][y])
                        c[k++] = dim ? y : x;
            nth_element(c, c+k/2, c+k);
            int louis = c[k/2];  // (co)median
            while (k--)
                total += abs(louis - c[k]);
        }
        return total;
    }
    

    Solution 2 ... sort ... 12 ms, O(mn log(mn))

    Sort the coordinates and use larrywang2014's way to add the travel distances.

    int minTotalDistance(vector<vector<int>>& grid) {
        int total = 0, X = grid.size(), Y = grid[0].size();
        for (int dim=0; dim<2; ++dim) {
            int i = 0, k = 0, c[X*Y];
            for (int x=0; x<X; ++x)
                for (int y=0; y<Y; ++y)
                    if (grid[x][y])
                        c[k++] = dim ? y : x;
            sort(c, c+k);
            while (i < --k)
                total += c[k] - c[i++];
        }
        return total;
    }

Log in to reply
 

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