Hashmap containsKey Complexity O(1)

HashMap containsValue Complexity O(n)

Lonely Pixel I

重点在空间的优化，时间复杂度上 two passes是一定要的。O(m+n) space trivial

public class Solution {
    public int findLonelyPixel(char[][] p) {
        if(p==null||p.length==0) return 0;
        HashMap<Integer,Integer> row = new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> col = new HashMap<Integer,Integer>();
        int m = p.length; int n = p[0].length;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(p[i][j]=='B'){
                    row.put(i,row.getOrDefault(i,0)+1);
                    col.put(j,col.getOrDefault(j,0)+1);
                }
            }
        int count = 0;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++){
                if(p[i][j]=='B'){
                   if(row.get(i)==1 && col.get(j)==1) count++;
                }
            }
       return count;
    }
}

O(m) space是建立一个col array，记录每个col里面B的数量。在第二次扫的时候， 如果当前row B的count＝1并且唯一存在'B'的col[pos]==1, ans++;

public class Solution {
    public int findLonelyPixel(char[][] picture) {
        if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;

        int[] colArray = new int[picture[0].length];
        for (int i = 0; i < picture.length; i++) {
            for (int j = 0; j < picture[0].length; j++) {
                if (picture[i][j] == 'B') colArray[j]++;
            }
        }

        int ret = 0;
        for (int i = 0; i < picture.length; i++) {
            int count = 0, pos = 0;
            for (int j = 0; j < picture[0].length; j++) {
                if (picture[i][j] == 'B') {
                    count++;
                    pos = j;
                }
            }
            if (count == 1 && colArray[pos] == 1) ret++;
        }
        return ret;
    }
}

这里space也有O(1)的解法，需要修改原数组，改变第一行的值。

思路是第一次pass的时候遇到‘B’后将该列 和 该行第一个元素char增1，‘B' 变成‘C’，‘W’变成‘X’，为了防止矩阵过大时，char会溢出，规定char最高增到‘Y’或者‘V’。因为第一行元素此时失效了，所以要统计firstRow count。

第二次pass的时候遇到‘B’时，如果此时是第一行遇到‘B‘， 可以确定该列是没有重复的’B‘， 如果firstrow count＝＝1， 第一行只有1个‘B’，count＋1；检查该行 和 该列第一个元素是否是‘C’ 或者‘X’， 如果是，count＋1。

public int findLonelyPixel(char[][] picture) {
    int n = picture.length, m = picture[0].length;

    int firstRowCount = 0;
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] == 'B') {   
                if (picture[0][j] < 'Y' && picture[0][j] != 'V') picture[0][j]++;
                if (i == 0) firstRowCount++;
                else if (picture[i][0] < 'Y' && picture[i][0] != 'V') picture[i][0]++;
            }

    int count = 0;
    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++) 
            if (picture[i][j] < 'W' && (picture[0][j] == 'C' || picture[0][j] == 'X')) { 
                if (i == 0) count += firstRowCount == 1 ? 1 : 0;
                else if (picture[i][0] == 'C' || picture[i][0] == 'X') count++;
            }

    return count;
}

Lonely Pixel II

这道题在1的基础上加了一个条件，需要有N行的line是一模一样的，所以需要一个hashmap来存line signature。

这里一个技巧是在进入枚举j列之前，先通过key得到N，判断i行是否有N个元素。如果不符合，就不用枚举j

public class Solution {
    public int findBlackPixel(char[][] p, int N) {
        if(p==null||p.length==0) return 0;
        HashMap<Integer,Integer> row = new HashMap<Integer,Integer>();
        HashMap<Integer,Integer> col = new HashMap<Integer,Integer>();
        HashMap<String, Integer> line = new HashMap<String, Integer>();
        int m = p.length; int n = p[0].length;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(p[i][j]=='B'){
                    row.put(i,row.getOrDefault(i,0)+1);
                    col.put(j,col.getOrDefault(j,0)+1);
                }
            }
            String key = getLine(i,p);
            line.put(key, line.getOrDefault(key, 0)+1);
         }
        int count = 0;
        for(int i=0;i<m;i++){
               String key = getLine(i,p);
            if(line.get(key)==N && row.containsKey(i)&&row.get(i)==N){
                for(int j=0;j<n;j++){
                    if(col.containsKey(j)&&col.get(j)==N&&p[i][j]=='B') {count++;}
                }
            }
        }
       return count;
    }

    public String getLine(int i, char[][] p){
        StringBuilder sb = new StringBuilder();
        for(int j=0;j<p[0].length;j++){
            sb.append(p[i][j]);
        }
        String key = sb.toString();
        return key;
    }
}