832.翻转图像

(Updated: )
LeetCode

Q

给定一个二进制矩阵 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]]

A

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// class Solution {
//     public int[][] flipAndInvertImage(int[][] A) {
//         for(int[] line:A){
//             line = reverse(line);
//             line = Invert(line);
//         }
//     }
// }

class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
        int C = A[0].length;
        for (int[] row: A)
            //小于行的中位数，游标自增
            for (int i = 0; i < (C + 1) / 2; ++i) {
                //异或1取反并翻转中位数两侧
                int tmp = row[i] ^ 1;
                row[i] = row[C - 1 - i] ^ 1;
                row[C - 1 - i] = tmp;
            }

        return A;
    }
}

  • 思路
    可以不使用额外的（非常数）空间来完成翻转和反转操作。对于 A[i][j]，将它和 A[i][c - j - 1] 进行交换（即翻转），其中 c 是数组 A 的列数。在交换的同时，可以将这两个数进行反转。

  • 时间复杂度
    O(M∗N)，其中 M 和 N 分别为数组 A 的行数和列数。

  • 空间复杂度
    O(1)