[LeetCode]832. Flipping an Image

发表于 | 分类于 | 评论数： | 阅读次数：
字数统计：650 字 | 阅读时长：3 分钟

832. 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:

1
2
3
4
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:

1
2
3
4
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> reversAndInvert(vector<int> &in) {
        int len = in.size();
        vector<int> out(len);
        for(int i = 0; i < len; ++i) {
            out[i] = !in.at(len-1-i);
        }
        return out;
    }
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        int len = A.size();
        vector<vector<int>> result(len);
        for(int i = 0; i < len; ++i) {
            result[i] = reversAndInvert(A.at(i));
        }
        return result;
    }
};

result

Runtime: 20 ms, faster than 21.52% of C++ online submissions for Flipping an Image.

Memory Usage: 9.3 MB, less than 100.00% of C++ online submissions for Flipping an Image.

预料到时间会比较高，毕竟时间复杂度是 （后面解释，慢竟然不是因为这个原因）。

方案二

从讨论区里面找到一个方案，再稍微修改下，使用了reverse函数，并通过引用修改原有元素，而且使用了异或操作。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    vector<vector<int>> flipAndInvertImage(vector<vector<int>>& A) {
        for (auto & row : A) {
            reverse(row.begin(), row.end());
            for (int & i: row) {
                i ^= 1;
            }
        }
        return A;
    }
};

result

Runtime: 12 ms, faster than 100.00% of C++ online submissions for Flipping an Image.

Memory Usage: 9.3 MB, less than 99.61% of C++ online submissions for Flipping an Image.

其实套路基本差不多，但是有个很关键的操作 i ^= 1;，这个异或操作比方案一的 ! 操作，效率高很多。

把方案一的 ! 操作，换成异或后，也得到了类似的效果，不过新开辟的vector就多了空间复杂度。

Runtime: 12 ms, faster than 100.00% of C++ online submissions for Flipping an Image.

Memory Usage: 9.5 MB, less than 99.22% of C++ online submissions for Flipping an Image.