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

描述

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。
提示:你可以假定该字符串只包含小写字母。

解题思路

最简单的方法应该是用hashMap先遍历一遍统计不同字符的个数,然后在第二遍遍历是寻找对应字符,如果遇到值为1的字符,返回即可。但由于提示说明字符串只包含小写字母,我们可以初始化一个长度为26的数组来代替hashMap。

代码如下

  public int firstUniqChar(String s) {
    int[] ints = new int[26];
    for (int i = 0; i <s.length(); i++) {
      ints[(s.charAt(i)-'a')]++;
    }
    for (int i = 0; i < s.length(); i++) {
      if (ints[(s.charAt(i)-'a')]==1){
        return i;
      }
    }
    return -1;
  }

运行结果:

9:15    info
                    解答成功:
                    执行耗时:7 ms,击败了77.54% 的Java用户
                    内存消耗:39.1 MB,击败了26.33% 的Java用户

题解

方法一:使用哈希表存储频数

class Solution {
    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;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二:使用哈希表存储索引

我们可以对方法一进行修改,使得第二次遍历的对象从字符串变为哈希映射。

具体地,对于哈希映射中的每一个键值对,键表示一个字符,值表示它的首次出现的索引(如果该字符只出现一次)或者 -1−1(如果该字符出现多次)。当我们第一次遍历字符串时,设当前遍历到的字符为 cc,如果 cc 不在哈希映射中,我们就将 cc 与它的索引作为一个键值对加入哈希映射中,否则我们将 cc 在哈希映射中对应的值修改为 -1−1。

在第一次遍历结束后,我们只需要再遍历一次哈希映射中的所有值,找出其中不为 -1−1 的最小值,即为第一个不重复字符的索引。如果哈希映射中的所有值均为 -1−1,我们就返回 -1−1。

class Solution {
    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;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法三:队列

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质,因此很适合用来找出第一个满足某个条件的元素。

具体地,我们使用与方法二相同的哈希映射,并且使用一个额外的队列,按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时,设当前遍历到的字符为 cc,如果 cc 不在哈希映射中,我们就将 cc 与它的索引作为一个二元组放入队尾,否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求,即我们不断地根据哈希映射中存储的值(是否为 -1−1)选择弹出队首的元素,直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后,如果队列为空,说明没有不重复的字符,返回 -1−1,否则队首的元素即为第一个不重复的字符以及其索引的二元组。

小贴士

在维护队列时,我们使用了「延迟删除」这一技巧。也就是说,即使队列中有一些字符出现了超过一次,但它只要不位于队首,那么就不会对答案造成影响,我们也就可以不用去删除它。只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。

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;
        }
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

小结

考虑使用队列和栈等数据结构解题

添加新评论