Leetcode Python超琐碎笔记: 832. Flipp

超琐碎 ≈ 完整记录 + 深入探究 + 任性吐槽

问题地址，难度：Easy，标签：Array

若有错误之处请予以指正:)

问题描述

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1

题意分析

这个问题分两步， 数组内容的翻转、数组内每个0/1值的反转，两步先后顺序无影响。反转0和1可选用两个简单函数，y=1-x或y=x^1（异或）。第三个点是如何进行整个图片矩阵（二维数组）的遍历。

我的实现及调优过程

方法1：76 ms

class Solution:
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        A = [row[::-1] for row in A]
        A = [list(map(lambda x: 1-x, row)) for row in A]
        return A

最符合我目前Python编码直觉（Pythonic？）的方法。切片-1步长完成数组翻转，map-lambda把反转函数map到数组中的每一个0-1值。

• 时间复杂度：NA
• 空间复杂度：NA

方法2：48 ms

class Solution:
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        A = [row[::-1] for row in A]
        A = [list(map(lambda x: x^1, row)) for row in A]
        return A

与方法1比较仅仅把0-1反转函数换成了异或运算，看来逻辑运算确实比数值快。

• 时间复杂度：NA
• 空间复杂度：NA

方法3：72 ms

class Solution:
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        for row in A:
            i = 0
            j = len(row) - 1
            while (i <= j):
                row[i], row[j] = row[j]^1, row[i]^1
                i += 1
                j -= 1
        return A

自己实现数组翻转、0-1反转和遍历。对于A中的每一行数组，生成头尾两个指针，将头尾指向的值先做0-1反转，再进行交换；将指针不断向中间移动，完成整个翻转。方法3比方法1快一点，比方法2慢很多。

• 时间复杂度：O(m*n) （m为矩阵行数，n为列数）
• 空间复杂度：O(m)

方法4：48 ms

class Solution:
    def flipAndInvertImage(self, A):
        """
        :type A: List[List[int]]
        :rtype: List[List[int]]
        """
        for row in A:
            for i in range((len(row)+1)//2): # for both even/odd row length
                row[i], row[~i] = row[~i]^1, row[i]^1
        return A

参考Leetcode上的解法，可以理解为方法3的一个小改进，使用了row[~i]来获得row[-i-1] = row[len(row) - 1 - i]（~是逻辑运算NOT，~(int) = -(int)-1），这样少用了一个指针。此外要配合这种方法，还需要确认交换的循环中，i在列数（每行的长度）为奇数和偶数的情况下都能拿到正确的取值范围。如果i超出正确范围，会把本来已正确交换的位置再错误地交换。我在这里使用了（数组长度+1）//2的方法，这样在两种情况下：

• 列数为奇数，以3为例：(3+1)//2 = 2，range后得到[0,1]
• 列数为偶数，以4为例：(4+1)//2 = 2，range后得到[0,1]

如果列数为奇数，i取到range的最大值时，最中间的值自己和自己交换（row[i]和row[~i]指向同一位置），冗余计算了，但是从复杂度上考虑无影响，并且真要优化也比较麻烦，需要先确认列数为奇数，还要确认i已取到range的最大值。

速度上与最快的方法2平齐。

• 时间复杂度：O(m*n) （m为矩阵行数，n为列数）
• 空间复杂度：O(m)