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

题目链接

Leetcode

题目描述

在一个字符串中找到第一个只出现一次的字符。若不存在则返回单空格。

Input: abacc
Output: b

解题思路

最直观的解法是使用 HashMap 对出现次数进行统计：字符作为 key，出现次数作为 value，遍历字符串每次都将 key 对应的 value 加 1。统计完后再按原字符串的顺序扫描一遍，第一个次数为 1 的字符就是答案。不能直接遍历 HashMap，因为 HashMap 不保留字符在字符串中出现的顺序。

考虑到要统计的字符范围有限，也可以使用整型数组代替 HashMap。ASCII 码只有 128 个字符，因此可以使用长度为 128 的整型数组来存储每个字符出现的次数。

public char dismantlingAction(String arr) {
    int[] cnts = new int[128];
    for (int i = 0; i < arr.length(); i++) {
        cnts[arr.charAt(i)]++;
    }
    for (int i = 0; i < arr.length(); i++) {
        if (cnts[arr.charAt(i)] == 1) {
            return arr.charAt(i);
        }
    }
    return ' ';
}

字符集大小固定，计数数组已经是 O(1) 空间。如果还想减少常数，需要区分的次数只有 0、1 和大于 1 三种，每个字符用两个比特位就能存储。

public char dismantlingAction(String arr) {
    BitSet bs1 = new BitSet(128);
    BitSet bs2 = new BitSet(128);
    for (int i = 0; i < arr.length(); i++) {
        char c = arr.charAt(i);
        if (!bs1.get(c) && !bs2.get(c)) {
            bs1.set(c);     // 0 0 -> 0 1
        } else if (bs1.get(c) && !bs2.get(c)) {
            bs2.set(c);     // 0 1 -> 1 1
        }
    }
    for (int i = 0; i < arr.length(); i++) {
        char c = arr.charAt(i);
        if (bs1.get(c) && !bs2.get(c)) {  // 0 1
            return c;
        }
    }
    return ' ';
}