[832][简单] 翻转图像

题目描述

832. 翻转图像

给定一个二进制矩阵 A, 我们想先水平翻转图像, 然后反转图像并返回结果。

水平翻转图片就是将图片的每一行都进行翻转, 即逆序。例如, 水平翻转 [1, 1, 0] 的结果是 [0, 1, 1]。

反转图片的意思是图片中的 0 全部被 1 替换, 1 全部被 0 替换。例如, 反转 [0, 1, 1] 的结果是 [1, 0, 0]。

示例 1:

输入: [[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]]；
      然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 2:

输入: [[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]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]]；
      然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

说明:

• 1 <= A.length = A[0].length <= 20

• 0 <= A[i][j] <= 1

解题思路

最直接的方法就是按题目描述的步骤, 按行循环, 每行先逆序, 后进行0/1变换. 相当于每行都需要遍历两次, 时间复杂度为$O(2N)$.

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for row in A:       
            for k, _ in enumerate(row):
                row[k] = 1 - row[k]
            i, j = 0, len(row) - 1
            while i < j:
                row[i], row[j] = row[j], row[i]
                i, j = i + 1, j - 1
        return A

但观察变换后的结果, 如果交换位置的两个数是不同的, 比如说一个是 1, 一个是 0, 那么先 10 反转, 则一个是 0, 一个是 1, 再左右翻转, 又变回一个是 1, 一个是 0. 这说明当两个数是不同的时候, 不用做任何事情. 只有当两个数相等的时候, 交换再翻转后相当于两个位置都分别做异或.

class Solution:
    def flipAndInvertImage(self, A: List[List[int]]) -> List[List[int]]:
        for row in A:
            for i in range((len(row) + 1) // 2):
                if row[i] == row[-i - 1]:
                    row[i], row[-i - 1] = 1 - row[-i - 1], 1 - row[i]
        return A

遍历技巧

这里有一个遍历的技巧, 将数组逆序, 无论数组的长度$N$为奇数或偶数, 都可以只遍历一般的长度, 即遍历到索引$\lfloor (N + 1) / 2 \rfloor$之前停止. 这样会带来:

• 将遍历的次数减少一般

• 逆序问题可以转换成位置交换问题

参考资料

• Python3 多种解法详解（含最短1行法）