golang 解法, 执行用时: 12 ms, 内存消耗: 6.3 MB, 提交时间: 2023-10-22 10:22:47

func minTotalDistance(grid [][]int) int {
	col := make([]int,0)
	lst := make([]int,0)

	for i:=0; i<len(grid); i++ {
		for j:=0; j<len(grid[0]); j++ {
			if grid[i][j] == 1 {
				col = append(col,i)
				lst = append(lst,j)
			}
		}
	}
	sort.Ints(col)
	sort.Ints(lst)
	sum := 0
	i,j := 0,len(col)-1
	for i<j {
		sum += col[j]-col[i]
		sum += lst[j]-lst[i]
		i++
		j--
	}
	return sum
}

python3 解法, 执行用时: 60 ms, 内存消耗: 18 MB, 提交时间: 2023-10-22 10:22:30

class Solution:
    def minTotalDistance(self, grid: List[List[int]]) -> int:
        Row = len(grid)
        Col = len(grid[0])

        rs = []
        cs = []
        for r in range(Row):
            for c in range(Col):
                if grid[r][c] == 1:
                    rs.append(r)
                    cs.append(c)
        
        rs.sort()
        cs.sort()
        rn = len(rs)
        cn = len(cs)
        r_mid = rs[rn//2]
        c_mid = cs[cn//2]

        res = 0
        for r in range(Row):
            for c in range(Col):
                if grid[r][c] == 1:
                    res += abs(r - r_mid) + abs(c - c_mid)
        return res

java 解法, 执行用时: 7 ms, 内存消耗: 43.8 MB, 提交时间: 2023-10-22 10:21:54

class Solution {
    public int minTotalDistance(int[][] grid) {
        List<Integer> rows = collectRows(grid);
        List<Integer> cols = collectCols(grid);
        return minDistance1D(rows) + minDistance1D(cols);
    }

    private int minDistance1D(List<Integer> points) {
        int distance = 0;
        int i = 0;
        int j = points.size() - 1;
        while (i < j) {
            distance += points.get(j) - points.get(i);
            i++;
            j--;
        }
        return distance;
    }

    private List<Integer> collectRows(int[][] grid) {
        List<Integer> rows = new ArrayList<>();
        for (int row = 0; row < grid.length; row++) {
            for (int col = 0; col < grid[0].length; col++) {
                if (grid[row][col] == 1) {
                    rows.add(row);
                }
            }
        }
        return rows;
    }

    private List<Integer> collectCols(int[][] grid) {
        List<Integer> cols = new ArrayList<>();
        for (int col = 0; col < grid[0].length; col++) {
            for (int row = 0; row < grid.length; row++) {
                if (grid[row][col] == 1) {
                    cols.add(col);
                }
            }
        }
        return cols;
    }
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 11.9 MB, 提交时间: 2023-10-22 10:21:32

class Solution {
public:
    int minTotalDistance(vector<vector<int>>& grid) {
    	vector<int> X, Y;
    	int row = grid.size(), col = grid[0].size();
    	for (int i = 0; i < row; ++i)
    	{
    		for (int j = 0; j < col; ++j)
    		{
    			if (grid[i][j] == 1)
    			{
    				X.emplace_back(i);
    				Y.emplace_back(j);
    			}
    		}
    	}
    	sort(X.begin(), X.end());
    	sort(Y.begin(), Y.end());
    	int n = X.size();
    	int m = n >> 1;
    	int r = 0;
    	for (int i = 0; i < m; ++i)
    	{
    		r += X[n - i - 1] - X[i] + Y[n - i - 1] - Y[i];
    	}
    	return r;
    }
};