"Find the First Non Duplicate Character in a String"，了解哈希表与哈希图以保证插入顺序？

Question

我在firecode.io上做这个问题：

firstNonRepeatedCharacter( "abcdcd" ) --> 'a'
firstNonRepeatedCharacter( "cbcd" ) --> 'b'
firstNonRepeatedCharacter( "cdcd" ) --> null

我想出的解决方案是：

public static Character firstNonRepeatedCharacter(String str) {
    if (str == null) return null;
    Hashtable<Character, Integer> map = new Hashtable<Character, Integer>();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
        } else {
            map.put(c, 1);
        }
    }
    for (Character key : map.keySet()) {
        if (map.get(key) == 1) return key;
    }
    return null;
}

这是第一个测试案例失败的，并得到了：

firstNonRepeatedCharacter( "abcdcd" ) --> 'b'  // 'a' is correct

我意识到自己在假设插入顺序，所以我尝试了HashMap：

Map<Character, Integer> map = new HashMap<Character, Integer>();

最终通过了所有情况。

基于我阅读的内容，HashMap通常应在Hashtable上使用，但是HashMap甚至不能保证支持顺序，而LinkedHashMap则使用。它是否正确？我只是对测试用例很幸运，应该使用LinkedHashMap？

Answer 1

按照您的建议，在这里使用LinkedHashMap将非常有帮助，因为它可以跟踪插入地图中的键值对的插入顺序。因此，您需要做的就是仅对看到每个字母的次数进行反击。当您插入一个字符时，将计数器递增，除非从未见过，否则您会在其中分配一个值。然后，按插入顺序走下列表，然后返回仅出现一次的第一个字符。这是一个工作实现：

public static Character firstNonRepeatedCharacter(String str) {
    if (str == null) return null;
    // use a LinkedHashMap, which maintains insertion order
    // keep a counter of how many times a character is observed, which defaults to 1
    // for characters never seen before
    LinkedHashMap<Character, Integer> map = new LinkedHashMap<>();
    for (int i = 0; i < str.length(); i++) {
        Integer cnt = map.get(str.charAt(i));
        map.put(str.charAt(i), cnt == null ? 1 : cnt.intValue() + 1);
    }
    // now just walk the list, in insertion order, and return the first key
    // whose value is 1 (indicating that it never got repeated)
    for (Map.Entry<Character, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }
    // return null if no such key appearing only once occurred in the string
    return null;
}

演示：

rextester