Clear solution in Java


  • 1
    M
    /*
        -- x方向的距离和y方向的距离分开考虑.
        -- 在median处(假设共有n个点, median处的点是第floor(n/2)个)的点到所有点的距离之和最小.
           若向左/向右移动一小段距离, 显然距离之和增大.
    */
    public class Solution {
        public int minTotalDistance(int[][] grid) {
            if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
            int height = grid.length, width = grid[0].length;
            int sum = 0;
            List<Integer> coord = new ArrayList<>();
            // project to x-axis
            for (int i = 0; i < width; ++i) {
                for (int j = 0; j < height; ++j) {
                    if (grid[j][i] == 1) coord.add(i);
                }
            }
            int median = coord.get(coord.size() / 2);
            for (int x: coord) sum += Math.abs(median - x);
            coord.clear();
            // project to y-axis
            for (int i = 0; i < height; ++i) {
                for (int j = 0; j < width; ++j) {
                    if (grid[i][j] == 1) coord.add(i);
                }
            }
            median = coord.get(coord.size() / 2);
            for (int y: coord) sum += Math.abs(median - y);
            return sum;
        }
    }

Log in to reply
 

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