跳转至

832. 翻转图像

题目描述

给定一个 n x n 的二进制矩阵 image ，先 水平 翻转图像，然后 反转 图像并返回 结果 。

水平翻转图片就是将图片的每一行都进行翻转，即逆序。

  • 例如，水平翻转 [1,1,0] 的结果是 [0,1,1]。

反转图片的意思是图片中的 0 全部被 1 替换， 1 全部被 0 替换。

  • 例如，反转 [0,1,1] 的结果是 [1,0,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]]；
     然后反转图片: [[1,0,0],[0,1,0],[1,1,1]]

示例 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]]
解释：首先翻转每一行: [[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]]

 

提示：

  • n == image.length
  • n == image[i].length
  • 1 <= n <= 20
  • images[i][j] == 0 或 1.

解法

方法一：双指针

思考

每行先水平翻转再取反。\(n\le 20\)，可在原数组上用首尾双指针同时完成两步。

若两端相等，翻转后仍相等，取反使它们同时变号；若两端不等，翻转加取反恰好互换，无需改值。中间单独一格只取反。

我们可以遍历矩阵，对于遍历到的每一行 \(\textit{row}\)，我们使用双指针 \(i\) 和 \(j\) 分别指向该行的首尾元素，如果 \(\textit{row}[i] = \textit{row}[j]\)，交换后两者的值仍然保持不变，因此，我们只需要对 \(\textit{row}[i]\) 和 \(\textit{row}[j]\) 进行异或反转即可，然后将 \(i\) 和 \(j\) 分别向中间移动一位，直到 \(i \geq j\)。如果 \(\textit{row}[i] \neq \textit{row}[j]\)，此时交换后再反转两者的值，仍然保持不变，因此，可以不进行任何操作。

最后，如果 \(i = j\)，我们直接对 \(\textit{row}[i]\) 进行反转即可。

时间复杂度 \(O(n^2)\)，其中 \(n\) 是矩阵的行数或列数。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def flipAndInvertImage(self, image: List[List[int]]) -> List[List[int]]:
        n = len(image)
        for row in image:
            i, j = 0, n - 1
            while i < j:
                if row[i] == row[j]:
                    row[i] ^= 1
                    row[j] ^= 1
                i, j = i + 1, j - 1
            if i == j:
                row[i] ^= 1
        return image

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    public int[][] flipAndInvertImage(int[][] image) {
        for (var row : image) {
            int i = 0, j = row.length - 1;
            for (; i < j; ++i, --j) {
                if (row[i] == row[j]) {
                    row[i] ^= 1;
                    row[j] ^= 1;
                }
            }
            if (i == j) {
                row[i] ^= 1;
            }
        }
        return image;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& image) {
        for (auto& row : image) {
            int i = 0, j = row.size() - 1;
            for (; i < j; ++i, --j) {
                if (row[i] == row[j]) {
                    row[i] ^= 1;
                    row[j] ^= 1;
                }
            }
            if (i == j) {
                row[i] ^= 1;
            }
        }
        return image;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
func flipAndInvertImage(image [][]int) [][]int {
    for _, row := range image {
        i, j := 0, len(row)-1
        for ; i < j; i, j = i+1, j-1 {
            if row[i] == row[j] {
                row[i] ^= 1
                row[j] ^= 1
            }
        }
        if i == j {
            row[i] ^= 1
        }
    }
    return image
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number[][]} image
 * @return {number[][]}
 */
var flipAndInvertImage = function (image) {
    for (const row of image) {
        let i = 0;
        let j = row.length - 1;
        for (; i < j; ++i, --j) {
            if (row[i] == row[j]) {
                row[i] ^= 1;
                row[j] ^= 1;
            }
        }
        if (i == j) {
            row[i] ^= 1;
        }
    }
    return image;
};

评论