Array 832 翻转图像

2020-10-28

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

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

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

思路：

将每行的数字进行翻转
0，1 替换

特殊情况

public int[][] flipAndInvertImage(int[][] A) {       
       for(int[] arr:A){
           // 将每行的数字进行翻转
           int i = 0,j = arr.length - 1;
           while(i <= j){
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               i++;
               j--;
           }
           
           for(int k = 0;k < arr.length ;k++){
               arr[k] = arr[k] == 0 ? 1 : 0;
           } 
       }
       return A;
   }

时间复杂度：$O(n^2)$

空间复杂度：只需要存储常数的额外空间

a^b : 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

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

for(int[] arr:A){
    int len = A[0].length;
    for(int i = 0;i < (len + 1)/2;i++){
        int temp = arr[i]^1;
        arr[i] = arr[len-1-i]^1;
        arr[len-1-i] = temp; 
     } 
}

异或运算符，双指针可以用 int i = 0;i < (len + 1)/2;i++ 和 arr[len-1-i]。

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

空间复杂度：O(1)