8_哈希.md

哈希

1、第一个只出现一次的字符位置

第一个只出现一次的字符位置

//思路一：
public int FirstNotRepeatingChar(String str) {
    int[] freq = new int[256];

    for(char c:str.toCharArray()){
        freq[c]++;
    }

    for(int i=0;i<str.length();i++){
        if(freq[str.charAt(i)]==1){
            return i;
        }
    }
    return -1;
}

//思路二：
// 需要优化空间复杂度，可以使用 BitSet
// BitSet 按位操作，每一位的值只有两种 0 或者 1，来表示某个值是否出现过。
// 如果字符出现的次数 >= 2，则表示未多个
// 所以只需要 2 位就可表示字符出现的次数，即 0次(00)、1次(01)或者多次(11)

public int FirstNotRepeatingChar(String str) {
    BitSet bitSet = new BitSet(256);
    BitSet bitSet2 = new BitSet(256);

    for(char c:str.toCharArray()){
        if(!bitSet.get(c) && !bitSet2.get(c)){ //00
            // c 原来出现次数 0次，加入 c 后出现次数为 1
            bitSet2.set(c);
        }
        else if(!bitSet.get(c) && bitSet2.get(c)){ //01 
            // c 原来出现次数 1 次，加入 c 后出现次数为 3 (3 表示多次)
            bitSet.set(c);
        }
    }

    for(int i=0;i<str.length();i++){
        char c= str.charAt(i);
        if(!bitSet.get(c) && bitSet2.get(c)){
            return i;
        }
    }

    return -1;
}