java - 字符串数组中的第一个唯一字符串

Question

给定一个字符串数组，如何找到数组中第一个唯一的字符串元素

public static String UniqueString(String[] s) {

    String str ="";

        for(int i=0;i<s.length;i++) {
            for(int j=i+1;j<s.length;j++) {
                System.out.println(s[i]+" "+s[j]);
                str = s[i];
                if(str==s[j]) {
                   break;
                }

                }if(!(str==s[i+1])){
                    return str;
                }

    }

    return str;
    }

因此 {Dog,Cat,Dog,Wolf,lion} 的字符串数组将返回为 Cat

Answer 1

您的方法随着列表的大小呈二次方增长。有一种更好的方法，它的列表大小基本上是线性的，即使用从字符串到出现次数的有序映射。使用一次遍历列表来构建映射，然后一次遍历映射来查找计数为 1 的第一个元素(如果有)。您可以使用 LinkedHashMap来实现这一点。

public static String uniqueString(String[] list) {
    Integer ZERO = 0; // to avoid repeated autoboxing below
    final LinkedHashMap<String, Integer> map = new LinkedHashMap<>(list.size());

    // build the map
    for (String s : list) {
        Integer count = map.getOrDefault(s, ZERO);
        map.put(s, count + 1);
    }

    // find the first unique entry. Note that set order is deterministic here.
    for (Set.Entry<String, Integer> entry : map.entrySet()) {
        if (entry.getValue() == 1) {
            return entry.getKey();
        }
    }

    // if we get this far, there was no unique string in the list
    return "";
}

请注意，您可以使用任何类型的 Map 实现(包括 HashMap)，并通过替换第二个循环来放弃 LinkedHashMap 的排序属性循环遍历原始列表:

for (String s : list) {
    if (map.get(s) == 1) {
        return s;
    }
}

但是，如果列表中有很多重复的字符串，则迭代 map 可能需要更少的迭代。因此，不妨使用 LinkedHashMap 的附加功能，与 HashMap 相比，您获得的性能损失非常小。