LonelyPixelIOPT [source code]

public class LonelyPixelIOPT {
static
/******************************************************************************/
public class Solution {
    public int findLonelyPixel(char[][] picture) {
        int m = picture.length, n = picture[0].length;
        int[] row = new int[m];

        int[] col = new int[n];
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    col[j]++;
                    if (row[i] == 0)
                        row[i] = j + 1;
                    else row[i] = -1;
                }
            }
        }

        for (int r : row)
            if (r > 0 && col[r - 1] == 1)
                res++;

        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LonelyPixelIOPT.Solution tester = new LonelyPixelIOPT.Solution();
        char[][][] inputs = {
            {{'W', 'W', 'B'},
            {'W', 'B', 'W'},
            {'B', 'W', 'W'}},
            {{'B', 'W'},
            {'W', 'B'}},
        };
        int[] answers = {
            3,
            2,
        };
        for (int i = 0; i < inputs.length; i++) {
            char[][] picture = inputs[i];
            int answer = answers[i];
            System.out.println(Printer.seperator());
            int output = tester.findLonelyPixel(picture);
            System.out.println(Printer.wrapColor(Matrix.printMatrix(picture), "magenta") + " -> " + output + Printer.wrapColor(", expected: " + answer, answer == output ? "green" : "red"));
        }
    }
}

这个算法在performance方面其实没有什么特别的地方, 就是觉得想法有点意思, 所以保存下来;

大概的意思就是记录没一行, the column index of the leftmost black pixel. if duplicates in the row, then just store -1 to signal the duplicate;

然后结束了之后,再对row进行分析, 如果是-1, 那肯定就是有duplicate了, 跳过; 如果是正数, 说明这一行就一个黑点, 但是你还要查询一下这个leftmost所在的这一列, 是不是也只有一个黑点; 如果是, 那么就找到了一个lonely;

我本来记录下来的时候其实是因为认为这个算法是使用了record leftmost这个技术的, 这个技术之前好像也大概总结过, leftmost和rightmost好像是有专门的用法的, 具体是什么忘记了, 后面翻一翻看;

但是实际上这一题并不是非常的依赖leftmost这个东西, 他其实每一行和每一列都有专门的判断手段; 每一行保存的信息, 其实仅靠leftmost index并不能保证最后的算法拥有足够的信息;

Problem Description

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.

Example:
Input:
[['W', 'W', 'B'],
['W', 'B', 'W'],
['B', 'W', 'W']]

Output: 3
Explanation: All the three 'B's are black lonely pixels.
Note:
The range of width and height of the input 2D array is [1,500].
Difficulty:Medium
Total Accepted:5.6K
Total Submissions:10.3K
Contributor: fallcreek
Companies
google
Related Topics
array depth-first search