Medium

题目描述

给你一个 m x n 的二进制矩阵 grid。

如果一行或一列的值正读和反读都相同，则认为该行或列是回文的。

你可以将 grid 中任意数量的格子从 0 翻转为 1，或者从 1 翻转为 0。

返回使所有行回文或所有列回文所需的最少翻转次数。

示例 1：

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]
输出：2
解释：
翻转高亮的格子可以使所有行都回文。

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]
输出：1
解释：
翻转高亮的格子可以使所有列都回文。

示例 3：

输入：grid = [[1],[0]]
输出：0
解释：
所有行都已经回文。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m * n <= 2 * 10^5
  • 0 <= grid[i][j] <= 1

解题思路

这道题要求我们找到最少的翻转次数，使得矩阵的所有行都回文或者所有列都回文。关键在于我们只需要选择其中一种策略。

解题思路

由于我们可以选择让所有行回文或所有列回文，所以需要分别计算两种情况的翻转次数，然后取最小值。

方法一：分别计算行回文和列回文的代价

核心思想：

  1. 计算行回文代价：对每一行，使用双指针从两端向中间检查，如果对应位置的值不同就需要翻转其中一个
  2. 计算列回文代价：对每一列，同样使用双指针检查对称位置是否相同
  3. 返回两种代价的最小值

具体步骤：

  • 遍历每一行，对于第 i 行，比较 grid[i][j] 和 grid[i][n-1-j] 是否相等
  • 遍历每一列，对于第 j 列，比较 grid[i][j] 和 grid[m-1-i][j] 是否相等
  • 每当发现不匹配时，翻转次数加1（因为我们只需要翻转其中一个元素）

这种方法时间复杂度为 O(m×n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int minFlips(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        
        // 计算使所有行回文的翻转次数
        int rowFlips = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (grid[i][j] != grid[i][n - 1 - j]) {
                    rowFlips++;
                }
            }
        }
        
        // 计算使所有列回文的翻转次数
        int colFlips = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m / 2; i++) {
                if (grid[i][j] != grid[m - 1 - i][j]) {
                    colFlips++;
                }
            }
        }
        
        return min(rowFlips, colFlips);
    }
};

class Solution:
    def minFlips(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        # 计算使所有行回文的翻转次数
        row_flips = 0
        for i in range(m):
            for j in range(n // 2):
                if grid[i][j] != grid[i][n - 1 - j]:
                    row_flips += 1
        
        # 计算使所有列回文的翻转次数
        col_flips = 0
        for j in range(n):
            for i in range(m // 2):
                if grid[i][j] != grid[m - 1 - i][j]:
                    col_flips += 1
        
        return min(row_flips, col_flips)

public class Solution {
    public int MinFlips(int[][] grid) {
        int m = grid.Length;
        int n = grid[0].Length;
        
        // 计算使所有行回文的翻转次数
        int rowFlips = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                if (grid[i][j] != grid[i][n - 1 - j]) {
                    rowFlips++;
                }
            }
        }
        
        // 计算使所有列回文的翻转次数
        int colFlips = 0;
        for (int j = 0; j < n; j++) {
            for (int i = 0; i < m / 2; i++) {
                if (grid[i][j] != grid[m - 1 - i][j]) {
                    colFlips++;
                }
            }
        }
        
        return Math.Min(rowFlips, colFlips);
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minFlips = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    // 计算使所有行回文的翻转次数
    let rowFlips = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < Math.floor(n / 2); j++) {
            if (grid[i][j] !== grid[i][n - 1 - j]) {
                rowFlips++;
            }
        }
    }
    
    // 计算使所有列回文的翻转次数
    let colFlips = 0;
    for (let j = 0; j < n; j++) {
        for (let i = 0; i < Math.floor(m / 2); i++) {
            if (grid[i][j] !== grid[m - 1 - i][j]) {
                colFlips++;
            }
        }
    }
    
    return Math.min(rowFlips, colFlips);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m×n)需要遍历整个矩阵检查所有行和列
空间复杂度O(1)只使用常数额外空间存储计数器

相关题目