我写了下面的代码来检测字符串中的第一个重复字符.
public static int detectDuplicate(String source) {
boolean found = false;
int index = -1;
final long start = System.currentTimeMillis();
final int length = source.length();
for(int outerIndex = 0; outerIndex < length && !found; outerIndex++) {
boolean shiftPointer = false;
for(int innerIndex = outerIndex + 1; innerIndex < length && !shiftPointer; innerIndex++ ) {
if ( source.charAt(outerIndex) == source.charAt(innerIndex)) {
found = true;
index = outerIndex;
} else {
shiftPointer = true;
}
}
}
System.out.println("Time taken --> " + (System.currentTimeMillis() - start) + " ms. for string of length --> " + source.length());
return index;
}
我需要两件事的帮助：
>此算法的最坏情况复杂度是多少？ – 我的理解是O(n).
>这是最好的方法吗？有人可以提供更好的解决方案(如果有的话)吗？
谢谢,
NN
解决方法
正如其他人所提到的,你的算法是O(n ^ 2).这是一个O(N)算法,因为HashSet #add在恒定时间内运行(散列函数在桶中正确地分散元素) – 请注意,我最初将散列集的大小调整为最大大小以避免调整大小/重新散列：
public static int findDuplicate(String s) {
char[] chars = s.tocharArray();
Set<Character> uniqueChars = new HashSet<Character> (chars.length,1);
for (int i = 0; i < chars.length; i++) {
if (!uniqueChars.add(chars[i])) return i;
}
return -1;
}
注意：这将返回第一个副本的索引(即与前一个字符重复的第一个字符的索引).要返回该字符首次出现的索引,您需要将索引存储在Map< Character,Integer>中. (在这种情况下,Map#put也是O(1))：
public static int findDuplicate(String s) {
char[] chars = s.tocharArray();
Map<Character,Integer> uniqueChars = new HashMap<Character,Integer> (chars.length,1);
for (int i = 0; i < chars.length; i++) {
Integer prevIoUsIndex = uniqueChars.put(chars[i],i);
if (prevIoUsIndex != null) {
return prevIoUsIndex;
}
}
return -1;
}
