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

发表于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，387. First Unique Character in a String

先看题目描述

ryPukR.png

大意就是给定一个字符串，让我们返回其中第一个仅出现一次的字符的下标，若仅出现一次的字符不存在，则返回 -1

算法和思路

这题很简单，用一个哈希表维护字符串中每个字母的出现次数即可，先遍历一次字符串统计每个字母的出现次数，然后再遍历字符串，令当前遍历的字母为 c，若其对应的出现次数为 1，则返回其下标；若遍历完字符串也没找到出现次数为 1 的字母，则返回 -1

算法源码

由于题目中说了字符串中只包含小写字母，所以可以用一个长度为 26 的整型数组来代替哈希表，并且先将字符串 s 转化为字符数组也可以提高运行效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int firstUniqChar(String s) {
        int[] count = new int[26];
        char[] cs = s.toCharArray();
        for (char c : cs) {
            count[c - 'a']++;
        }
        for (int i = 0; i < cs.length; i++) {
            if (count[cs[i] - 'a'] == 1) {
                return i;
            }
        }
        return -1;
    }
}

下面是看题解看到的一个做法，里面使用了队列，并且使用到了自定义的一个类，但代码运行效率一般

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
28
29
30
class Solution {
    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)) {
                position.put(ch, i);
                queue.offer(new Pair(ch, i));
            } else {
                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;
        }
    }
}