翻转图像-LeetCode

832. 翻转图像

🎯 问题描述（来源于LeetCode）

描述：
给定一个二进制矩阵 image，先水平翻转每一行（即反转每一行的顺序），然后反转每个像素（0 变为 1，1 变为 0）。返回结果图像。

说明：

• 水平翻转：例如 [1,1,0] 变为 [0,1,1]。
• 反转像素：0 → 1，1 → 0。

示例：

• 示例 1：

输入: image = [[1,1,0],[1,0,1],[0,0,0]]
输出: [[1,0,0],[0,1,0],[1,1,1]]
解释: 先水平翻转每行得到 [[0,1,1],[1,0,1],[0,0,0]]，再反转像素得到结果。

• 示例 2：

输入: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

💻 解题思路

思路一：分两步（水平翻转 + 反转像素）

算法步骤

1. 遍历每一行 i，将该行水平翻转：image[i] = image[i][::-1]。
2. 再次遍历每一行和每个元素，将 0 变为 1，1 变为 0（或使用 1 - x）。
3. 返回修改后的 image。

思路一：代码实现

from typing import List

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        m, n = len(image), len(image[0])
        for i in range(m):
            image[i] = image[i][::-1]
        for i, row in enumerate(image):
            for j, x in enumerate(row):
                image[i][j] = 1 if x == 0 else 0
        return image

---

思路二：合并一步（双指针同时交换并反转）

算法步骤

1. 遍历每一行，使用双指针 l（左）和 r（右）指向行首和行尾。
2. 循环条件 l <= r（当 l == r 时，只需处理中间元素的反转）：
   • 交换并反转：row[l], row[r] = 1 - row[r], 1 - row[l]。
     这一步同时完成了水平翻转（交换左右元素）和像素反转（1 - x）。
   • 然后 l += 1，r -= 1。
3. 处理完所有行后返回 image。

思路二：代码实现（用户提供）

class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        for row in image:
            l, r = 0, len(row) - 1
            while l <= r:
                row[l], row[r] = 1 - row[r], 1 - row[l]
                l += 1
                r -= 1
        return image

📊 性能分析

• 时间复杂度：两种思路均为 $O(m \times n)$，每个元素访问常数次。
• 空间复杂度：
  • 思路一：每行切片产生新列表，额外 $O(n)$ 空间（但只在单行内，整体为 $O(m \times n)$ 的临时空间）。
  • 思路二：原地双指针交换，额外空间 $O(1)$，更优。

思考

思路一代码直观，易于理解，但使用了切片创建了新行，空间稍大。思路二将水平翻转和像素反转合并到一次遍历中，使用双指针同时完成交换和取反，不仅减少了遍历次数，还节省了空间，是本题的最优解。两种方法均可通过，推荐在实际编码中使用思路二，因为它更高效。