Easy | LeetCode 387. 字符串中的第一个唯一字符 | 哈希 | 哈希+队列

387. 字符串中的第一个唯一字符

给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示：你可以假定该字符串只包含小写字母。

解题思路

方法一： 哈希表 + 两次遍历

public int firstUniqChar(String s) {
    Map<Character, Integer> frequency = new HashMap<Character, Integer>();
    // 第一次遍历, 将所有元素使用哈希表计数
    for (int i = 0; i < s.length(); ++i) {
        char ch = s.charAt(i);
        frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
    }
    // 第二次遍历, 根据哈希表的计数值返回第一个只出现一次的字符
    for (int i = 0; i < s.length(); ++i) {
        if (frequency.get(s.charAt(i)) == 1) {
            return i;
        }
    }
    return -1;
}

方法二： 哈希表存储索引

这种思路和方法一类似, 不过存储时需要做改变, 在存储哈希表时, 如果某字符是第一次出现, 则将字符的索引作为Value存储, 如果不是第一个存储, 则将value修改为-1。

然后第二次遍历时, 不遍历原字符串, 而是采用遍历哈希表的方式, 找到value不为-1的所有value的最小值。

public int firstUniqChar(String s) {
    Map<Character, Integer> position = new HashMap<Character, Integer>();
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        char ch = s.charAt(i);
        if (position.containsKey(ch)) {
            position.put(ch, -1);
        } else {
            position.put(ch, i);
        }
    }
    int first = n;
    for (Map.Entry<Character, Integer> entry : position.entrySet()) {
        int pos = entry.getValue();
        if (pos != -1 && pos < first) {
            first = pos;
        }
    }
    if (first == n) {
        first = -1;
    }
    return first;
}

方法三： 队列

public int firstUniqChar(String s) {
    Map<Character, Integer> position = new HashMap<Character, Integer>();
    Queue<Pair> queue = new LinkedList<Pair>();
    int n = s.length();
    for (int i = 0; i < n; ++i) {
        char ch = s.charAt(i);
        if (!position.containsKey(ch)) {
            // 某字符第一个出现时, 在HashMap中记录出现的位置
            position.put(ch, i);
            // 并且将字符和出现的位置入队
            queue.offer(new Pair(ch, i));
        } else {
            // 如果这个字符不是第一次出现, 将其Value标记为-1
            position.put(ch, -1);
            // 然后将队列的队首的所有出现多次的元素出队。
            while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
                queue.poll();
            }
        }
    }
    // 返回队列的队首元素的下标 
    return queue.isEmpty() ? -1 : queue.poll().pos;
}

class Pair {
    char ch;
    int pos;

    Pair(char ch, int pos) {
        this.ch = ch;
        this.pos = pos;
    }
}