LeetCode Flipping an Image

本篇為LeetCode上演算法的簡單問題，Flipping an Image。

題目如下：

Given a binary matrix A, we want to flip the image horizontally, then invert it, and return the resulting image.

To flip an image horizontally means that each row of the image is reversed. For example, flipping [1, 1, 0] horizontally results in [0, 1, 1].

To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0. For example, inverting [0, 1, 1] results in [1, 0, 0].

Example 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Example 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Notes:

• 1 <= A.length = A[0].length <= 20
• 0 <= A[i][j] <= 1

將輸入參數陣列（元素由1, 0組合）中的每個元素位置水平翻轉後，再將0改為1，1改為0。主要還是利用前後對調的技巧，而0，1轉換就使用XOR位元運算子(Bitwise operator)。

public static int[][] flipAndInvertImage(int[][] A) {
    
    for(int[] ints : A) {
        int lastIndex = ints.length - 1;
        for(int i = 0; i < ints.length/2; i++) {
            int temp = ints[i] ^= 1;
            ints[i] = ints[lastIndex - i] ^= 1;
            ints[lastIndex - i] = temp;
        }
        if((ints.length & 1) != 0) { // if length is odd
            ints[ints.length / 2] ^= 1;
        }
    }
    return A;
}

時間複雜度為O(N)（精確一點說是O(N²/2) (n * n array)）