剑指 Offer 50. 第一个只出现一次的字符

LinkedHashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> charToUniqMap = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!charToUniqMap.containsKey(c)) {
                charToUniqMap.put(c, Boolean.TRUE);
            } else {
                charToUniqMap.put(c, Boolean.FALSE);
            }
        }

        for (Map.Entry<Character, Boolean> entry : charToUniqMap.entrySet()) {
            if (entry.getValue()) {
                return entry.getKey();
            }
        }

        return ' ';
    }
}

使用 LinkedHashMap 可以避免重复扫描原字符串。

Array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public char firstUniqChar(String s) {
        int[] countArray = new int[26];
        int[] indexArray = new int[26];
        Arrays.fill(indexArray, -1);

        for (int i = 0; i < s.length(); i++) {
            int offset = s.charAt(i) - 'a';
            countArray[offset]++;
            if (indexArray[offset] == -1) {
                indexArray[offset] = i;
            }
        }

        int minIndex = Integer.MAX_VALUE;
        char uniqChar = ' ';

        for (int i = 0; i < countArray.length; i++) {
            if (countArray[i] == 1 && indexArray[i] < minIndex) {
                minIndex = indexArray[i];
                uniqChar = (char) ('a' + i);
            }
        }

        return uniqChar;
    }
}

References

剑指 Offer 50. 第一个只出现一次的字符