在一个字符串中查找第一个非重复的字符

问题描述：编写一个函数，这个函数接受一个字符串作为参数，并返回第一个不重复的字符。例如，字符串"abbcda"，c是第一个不重复的字符。

解决方法：

方法一：使用linkedHashMap来记录字符的个数，因为LinkedHashMap维持了插入元素的顺序，所以当我们扫描字符串时，只需要迭代LinkedHashMap并返回值为1的元素。

实现代码如下：

public static char getNonRepeatCharacter(String str)
            throws Exception {
        Map<Character, Integer> counts = new LinkedHashMap<>();

        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }

        for (Map.Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1)
                return entry.getKey();
        }

        throw new Exception("don't find any non repeated character!");
}

方法二：在时间和空间上平衡，在一次遍历中找出不重复的字符，使用一个Set和一个List去分别保存重复和不重复的字符，当我们完成一个时间复杂度为O(n)的字符串扫描后，可以通过访问List来获得这个不重复的字符，该时间复杂度为O(1),因为List是有序的，可以通过get(0)来获得第一个元素。

实现代码如下：

public static char getNonRepeatCharacter(String str)
            throws Exception {
        Set<Character> repeated = new HashSet<>();
        List<Character> nonRepeated = new LinkedList<>();

        for (char c : str.toCharArray()) {
            if (repeated.contains(c))
                continue;

            if (nonRepeated.contains(c)) {
                nonRepeated.remove((Character)c);
                repeated.add(c);
            } else {
                nonRepeated.add(c);
            }
        }

        if (nonRepeated.size() > 0) {
            return nonRepeated.get(0);
        }

        throw new Exception("don't find any non repeated character!");
}

方法三：与方法二思路类似，使用HashMap，在第一扫描计算各个字符的现次数之后，再出次扫描字符串去找到第一个不重复的字符。

实现代码如下：

public static char getNonRepeatCharacter(String str)
            throws Exception {
        HashMap<Character, Integer> map = new HashMap<>();

        for (char c : str.toCharArray()) {
            map.put(c, map.containsKey(c) ? map.get(c) + 1 : 1);
        }

        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }

        throw new Exception("don't find any non repeated character!");
}

完整代码：点击