categories: [Blog,Algorithm]

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

  1.     public int firstUniqChar(String s) {
  2.         Map<Character, Integer> frequency = new HashMap<Character, Integer>();
  3.         for (int i = 0; i < s.length(); ++i) {
  4.             char ch = s.charAt(i);
  5.             frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
  6.         }
  7.         for (int i = 0; i < s.length(); ++i) {
  8.             if (frequency.get(s.charAt(i)) == 1) {
  9.                 return i;
  10.             }
  11.         }
  12.         return -1;
  13.     }
  15. 作者：LeetCode-Solution
  16. 链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/
  17. 来源：力扣（LeetCode）
  18. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. public int firstUniqChar(String s) {
  2.         Map<Character, Integer> position = new HashMap<Character, Integer>();
  3.         Queue<Pair> queue = new LinkedList<Pair>();
  4.         int n = s.length();
  5.         for (int i = 0; i < n; ++i) {
  6.             char ch = s.charAt(i);
  7.             if (!position.containsKey(ch)) {
  8.                 position.put(ch, i);
  9.                 queue.offer(new Pair(ch, i));
  10.             } else {
  11.                 position.put(ch, -1);//将队列头部重复的数据移除
  12.                 while (!queue.isEmpty() && position.get(queue.peek().ch) == -1) {
  13.                     queue.poll();
  14.                 }
  15.             }
  16.         }
  17.         return queue.isEmpty() ? -1 : queue.poll().pos;
  18.     }
  20.     class Pair {
  21.         char ch;
  22.         int pos;
  24.         Pair(char ch, int pos) {
  25.             this.ch = ch;
  26.             this.pos = pos;
  27.         }
  28.     }
  30. 作者：LeetCode-Solution
  31. 链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/

解析
小贴士

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string/solution/zi-fu-chuan-zhong-de-di-yi-ge-wei-yi-zi-x9rok/