387. First Unique Character in a String

题目：

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

链接：https://leetcode.com/problems/first-unique-character-in-a-string/#/description

3/20/2017

注意的问题：

不能在第7行里把s.charAt()从hm中删除，因为如果有字符出现奇数次，还是会保留在hm中的。

 1 public class Solution {
 2     public int firstUniqChar(String s) {
 3         HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
 4         int sLength = s.length();
 5         for(int i = 0; i < s.length(); i++) {
 6             if (!hm.containsKey(s.charAt(i))) hm.put(s.charAt(i), i);
 7             else hm.put(s.charAt(i), sLength);
 8         }
 9         int minIndex = sLength;
10         for(HashMap.Entry<Character, Integer> entry : hm.entrySet()) {
11             Integer v = entry.getValue();
12             if (v < minIndex) minIndex = v;
13         }
14         return minIndex == sLength? -1: minIndex;
15     }
16 }

其他人的解法：

1. 可以把freq的长度增到256

 1 public class Solution {
 2     public int firstUniqChar(String s) {
 3         int freq [] = new int[26];
 4         for(int i = 0; i < s.length(); i ++)
 5             freq [s.charAt(i) - 'a'] ++;
 6         for(int i = 0; i < s.length(); i ++)
 7             if(freq [s.charAt(i) - 'a'] == 1)
 8                 return i;
 9         return -1;
10     }
11 }

4/16/2017

BB电面准备

第一面的方法可能更快一些，不过时间复杂度都一样

public class Solution {
    public int firstUniqChar(String s) {
        Map<Character, Integer> m = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            m.put(s.charAt(i), m.getOrDefault(s.charAt(i), 0) + 1);
        }
        for (int i = 0; i < s.length(); i++) {
            if (m.get(s.charAt(i)) == 1) return i;
        }
        return -1;
    }
}