[LeetCode]--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.

用数组，简单粗暴，把字符个数都记录下来，最后遍历一下原来的字符串，判断再这个数组里面的个数就行。

public int firstUniqChar1(String s) {
        if (s == null || s.length() == 0)
            return -1;
        int[] count = new int[256];

        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            count[index]++;
        }

        for (int i = 0; i < s.length(); i++) {
            int index = s.charAt(i) - 'a';
            if (count[index] == 1)
                return i;
        }
        return -1;
    }

利用Map来记录。

public int firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return -1;
        }

        HashMap<Character, Integer> hashmap = new HashMap<Character, Integer>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (hashmap.containsKey(c)) {
                hashmap.put(c, hashmap.get(c) + 1);
            } else {
                hashmap.put(c, 1);
            }
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (hashmap.get(c) == 1) {
                return i;
            }
        }
        return -1;
    }

利用一个List一个Map来记录。用更多的空间来换取时间。

public int firstUniqChar(String s) {
            char[] cs=s.toCharArray();
            List<Character> list=new ArrayList<Character>();
            Map<Character,Integer> map=new HashMap<Character,Integer>();
            for (int i = 0; i < cs.length; i++) {
                Character c=cs[i];
                if (map.containsKey(c)) {
                    list.remove(c);
                }else{
                    list.add(c);
                    map.put(c,i);
                }
            }
            return list.size()==0?-1:map.get(list.get(0));
        }