调整矩阵使矩阵的行和列都为回文【算法题】

来源：大鱼竞技面试题

思路如下：

首先，可以先看第一行，如果要使第一行成为回文的话，需要先调整第一个数：

和1对应的是4，那么要么把1变成4，要么把4变成1

然后，再看一列，如果要使第一列成为回文的话，要么1变成9，要么9变成1

然后，再看整个矩阵，如果要变成回文，那么矩阵的四个角必须为相同的一个数

然后，这就转换为了找到一个数，这个数分别与这四个数的差再相加，和最小。进而可以转化为，在坐标轴上找到一个点，到这四个点的距离和最小。

可以证明，这个点必然在最中间区间的任意一点即可，在本例子中可以是4~9之间任意整数：

调节之后便如下图所示：

然后同理，再开始处理第二个元素：

可以选择3~10之间任意整数，这里选择3

然后，就是位置为(1, 0)的元素，因为这里行数为奇数，所以和(1, 0)位置对应的元素只有两个

同理，再调节下面两个元素即可：

其实自始至终，只需要遍历左上角一部分元素即可：

参考代码：

package per.rain;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
    public int solve(int[][] matrix) {
        int m = matrix.length;
        if (m == 0) return 0;
        int n = matrix[0].length;
        int sum = 0;
        int height = m / 2 - 1;
        int width = n / 2 - 1;
        for (int i = 0; i <= height; i++) {
            for (int j = 0; j <= width; j++) {
                List<Integer> list = new ArrayList<>();
                list.add(matrix[i][j]);
                list.add(matrix[i][n - 1 - j]);
                list.add(matrix[m - 1 - i][j]);
                list.add(matrix[m - 1 - i][n - 1 - j]);
                sum += helper(list);
            }
        }
        // 奇数行单独拿出来算
        if ((m & 1) == 1) {
            int mid = m / 2;
            for (int j = 0; j <= width; j++) {
                List<Integer> list = new ArrayList<>();
                list.add(matrix[mid][j]);
                list.add(matrix[mid][n - 1 - j]);
                sum += helper(list);
            }
        }
        // 奇数列单独拿出来算
        if ((n & 1) == 1) {
            int mid = n / 2;
            for (int i = 0; i < height; i++) {
                List<Integer> list = new ArrayList<>();
                list.add(matrix[i][mid]);
                list.add(matrix[m - 1 - i][mid]);
                sum += helper(list);
            }
        }
        return sum;
    }

    // 找到距离列表中元素距离和最小的点
    public int helper(List<Integer> nums) {
        Collections.sort(nums);
        int n = nums.size();
        int mid = nums.get(n / 2);
        int sum = 0;
        for (Integer num : nums) {
            sum += Math.abs(num - mid);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 18},
        };
        int res = new Solution().solve(matrix);
        System.out.println("res = " + res);
    }
}
复制代码