因此，我面临一个问题。 “确定字符串是否包含所有唯一字符”
因此，我写了这个解决方案，将每个字符添加到集合中，但是如果该字符已经存在，则返回false。
private static boolean allUniqueCharacters(String s) {
Set<Character> charSet = new HashSet<Character>();
for (int i = 0; i < s.length(); i++) {
char currentChar = s.charAt(i);
if (!charSet.contains(currentChar)) {
charSet.add(currentChar);
} else {
return false;
}
}
return true;
}
根据我正在阅读的书，这是“最佳解决方案”
public static boolean isUniqueChars2(String str) {
if (str.length() > 128)
return false;
boolean[] char_set = new boolean[128];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) {
return false;
}
char_set[val] = true;
}
return true;
}
我的问题是，我的实现是否比提出的实现慢？我以为是这样，但是如果Hash查找为O(1)，它们的复杂度是否相同？
谢谢。
最佳答案
正如Amadan在评论中所说，这两个解决方案具有相同的时间复杂度O(n)，因为您有一个遍历字符串的for循环，并且在for循环中执行了恒定时间的操作。这意味着运行方法所花费的时间随着字符串的长度线性增加。
请注意，时间复杂度与更改输入大小时所花费的时间有关。这与大小相同的数据有多快无关。
对于相同的字符串，“最佳”解决方案应该更快，因为集合在数组上会有一些开销。处理数组比处理集合要快。但是，要使“最佳”解决方案真正起作用，您将需要一个长度为2 ^ 16的数组。那就是有多少个不同的char值。您还需要删除长度大于128的字符串的检查。
这是时空折衷的众多示例之一。如果您希望它运行得更快，则需要更多空间。如果要节省空间，则必须变慢。