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

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

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

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

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

示例:

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

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

解题思路

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

public int firstUniqChar(String s) {
    MapCharacter, Integer frequency = new HashMapCharacter, 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) {
    MapCharacter, Integer position = new HashMapCharacter, 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.EntryCharacter, 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) {
    MapCharacter, Integer position = new HashMapCharacter, Integer();
    QueuePair queue = new LinkedListPair();
    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;
    }
}