LeetCode刷题实战531：孤独像素 I

栈长 • 2022年2月19日 13:52 • 编程技术 • 阅读 414

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 孤独像素 I，我们先来看题面：

https://leetcode-cn.com/problems/lonely-pixel-i/

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.

A black lonely pixel is character ‘B’ that located at a specific position where the same row and same column don’t have any other black pixels.

给定一幅黑白像素组成的图像, 计算黑色孤独像素的数量。

图像由一个由‘B’和‘W’组成二维字符数组表示, ‘B’和‘W’分别代表黑色像素和白色像素。

黑色孤独像素指的是在同一行和同一列不存在其他黑色像素的黑色像素。

示例

示例:
输入: 
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]

输出: 3
解析: 全部三个'B'都是黑色孤独像素。
 
注意:
输入二维数组行和列的范围是 [1,500]。

解题

https://blog.csdn.net/qq_29051413/article/details/108617060

定义两个数组 row[] 和 col[]。

row[i] 表示第 i 行总共有多少个 ‘B’。

col[j] 表示第 j 列总共有多少个 ‘B’。

遍历 picture[][]，统计每一行每一列分别总共有多少个 ‘B’，同时把 ‘B’ 的坐标保存在一个 List 中。

遍历 List ：若 row[i] == col[j] == 1，说明 (i,j) 是一个孤独的像素，孤独像素的数量加一。

时间复杂度：O(kmn)，m为行数，n为列数，k为黑色像素的数量。

class Solution {
    public int findLonelyPixel(char[][] picture) {
        int ans = 0;
        int rowN = picture.length;
        int colN = picture[0].length;
        int[] row = new int[rowN];
        int[] col = new int[colN];
        List<Integer[]> list = new ArrayList<>();
        for (int i = 0; i < rowN; i++) {
            for (int j = 0; j < colN; j++) {
                if (picture[i][j] == 'B') {
                    row[i]++;
                    col[j]++;
                    list.add(new Integer[]{i, j});
                }
            }
        }
        for (Integer[] blackPoint : list) {
            int i = blackPoint[0];
            int j = blackPoint[1];
            if (row[i] == 1 && row[i] == col[j]) {
                ans++;
            }
        }
        return ans;
    }
}