Question

832. 翻转图像

English Version

题目描述

给定一个

 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.

解法

方法一：双指针

我们可以遍历矩阵，对于遍历到的每一行 $row$：

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

最后，如果 $i = j$，我们直接对 $row[i]$ 进行反转即可。

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

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

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;
  }
}

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;
  }
};

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
}

/**
 * @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;
};