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

Question

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

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}的String数组将返回为Cat

Answer 1

您的方法随列表的大小成平方增长。有一种更好的方法，它在列表大小上基本上是线性的，即使用从字符串到出现次数的有序映射。使用一次遍历列表来构建地图，然后一次遍历地图以找到计数为1的第一个元素（如果有）。可以使用a 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;
    }
}

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