算法题翻转图像-平芜编程栈

832. 翻转图像

问题描述

给定一个n x n的二进制矩阵image，对其进行水平翻转后再对每个元素进行反转（0变1，1变0）。

水平翻转：将每一行的元素顺序颠倒
反转：将每个 0 变为 1，每个 1 变为 0

要求原地修改矩阵并返回结果。

示例：

输入: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]]

输入: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]]

算法思路

双指针：

核心：
- 水平翻转 + 反转可以同时进行
- 对于每一行，使用双指针从两端向中间移动
- 交换两个位置的元素时，同时进行反转操作
反转：
- 使用异或操作：value ^ 1可以实现 0↔1 的翻转
- 或者使用1 - value

代码实现

方法一：双指针

classSolution{/** * 翻转图像：水平翻转每一行，然后反转每个元素（0变1，1变0） * 使用双指针原地操作，时间复杂度O(n²)，空间复杂度O(1) * * @param image n x n 的二进制矩阵 * @return 翻转后的图像 */publicint[][]flipAndInvertImage(int[][]image){intn=image.length;// 遍历每一行for(inti=0;i<n;i++){intleft=0;// 左指针intright=n-1;// 右指针// 双指针向中间移动while(left<right){// 交换左右元素并同时反转// 使用异或操作进行反转：0^1=1, 1^1=0inttemp=image[i][left]^1;image[i][left]=image[i][right]^1;image[i][right]=temp;left++;right--;}// 如果行长度为奇数，处理中间元素（只需反转）if(left==right){image[i][left]^=1;}}returnimage;}}

方法二：分步

classSolution{/** * 分步实现：先水平翻转，再反转每个元素 * * @param image 输入图像 * @return 翻转后的图像 */publicint[][]flipAndInvertImage(int[][]image){intn=image.length;// 水平翻转每一行for(inti=0;i<n;i++){intleft=0;intright=n-1;while(left<right){// 交换元素inttemp=image[i][left];image[i][left]=image[i][right];image[i][right]=temp;left++;right--;}}// 反转每个元素for(inti=0;i<n;i++){for(intj=0;j<n;j++){image[i][j]^=1;// 或者 image[i][j] = 1 - image[i][j];}}returnimage;}}

方法三：使用额外空间

classSolution{/** * 使用额外空间 * * @param image 输入图像 * @return 翻转后的图像 */publicint[][]flipAndInvertImage(int[][]image){intn=image.length;int[][]result=newint[n][n];for(inti=0;i<n;i++){for(intj=0;j<n;j++){// result[i][j] = 反转(image[i][n-1-j])result[i][j]=image[i][n-1-j]^1;}}returnresult;}}

算法分析

时间复杂度：O(n²)
- 需要处理矩阵中的每个元素一次
- 双指针中每个元素只被访问一次
空间复杂度：O(1)
- 原地修改，只使用常数额外空间

算法过程

输入：image = [[1,1,0],[1,0,1],[0,0,0]]

方法一：

处理第0行[1,1,0]：

left=0, right=2：交换image[0][0]和image[0][2]并反转
- temp = 1^1 = 0
- image[0][0] = 0^1 = 1
- image[0][2] = 0
- 行变为[1,1,0]
left=1, right=1：中间元素，image[0][1] ^= 1→1^1 = 0
最终第0行：[1,0,0]

处理第1行[1,0,1]：

left=0, right=2：交换并反转
- temp = 1^1 = 0
- image[1][0] = 1^1 = 0
- image[1][2] = 0
- 行变为[0,0,0]
left=1, right=1：中间元素，image[1][1] ^= 1→0^1 = 1
最终第1行：[0,1,0]

处理第2行[0,0,0]：

left=0, right=2：交换并反转
- temp = 0^1 = 1
- image[2][0] = 0^1 = 1
- image[2][2] = 1
- 行变为[1,0,1]
left=1, right=1：中间元素，image[2][1] ^= 1→0^1 = 1
最终第2行：[1,1,1]

最终结果：

[[1,0,0],[0,1,0],[1,1,1]]

测试用例

importjava.util.Arrays;publicclassMain{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[][]image1={{1,1,0},{1,0,1},{0,0,0}};int[][]result1=solution.flipAndInvertImage(image1);System.out.println("Test 1: "+Arrays.deepToString(result1));// [[1,0,0],[0,1,0],[1,1,1]]// 测试用例2：4x4矩阵int[][]image2={{1,1,0,0},{1,0,0,1},{0,1,1,1},{1,0,1,0}};int[][]result2=solution.flipAndInvertImage(image2);System.out.println("Test 2: "+Arrays.deepToString(result2));// [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]// 测试用例3：全1矩阵int[][]image3={{1,1,1},{1,1,1},{1,1,1}};int[][]result3=solution.flipAndInvertImage(image3);System.out.println("Test 3: "+Arrays.deepToString(result3));// [[0,0,0],[0,0,0],[0,0,0]]// 测试用例4：全0矩阵int[][]image4={{0,0,0},{0,0,0},{0,0,0}};int[][]result4=solution.flipAndInvertImage(image4);System.out.println("Test 4: "+Arrays.deepToString(result4));// [[1,1,1],[1,1,1],[1,1,1]]// 测试用例5：单元素矩阵int[][]image5={{1}};int[][]result5=solution.flipAndInvertImage(image5);System.out.println("Test 5: "+Arrays.deepToString(result5));// [[0]]int[][]image6={{0}};int[][]result6=solution.flipAndInvertImage(image6);System.out.println("Test 6: "+Arrays.deepToString(result6));// [[1]]// 测试用例6：2x2矩阵int[][]image7={{1,0},{0,1}};int[][]result7=solution.flipAndInvertImage(image7);System.out.println("Test 7: "+Arrays.deepToString(result7));// [[1,0],[0,1]]}}