有人可以验证一下这段代码的阶复杂度是否为 n(logn) 吗?如果不是,您能解释一下您的答案吗?我非常感谢您的帮助
public static boolean isDuplicate(String s){
char[] sArray = s.toCharArray();
for(int i=0;i<sArray.length/2;i++){
for(int j=sArray.length/2+1;j<sArray.length;j++){
if(sArray[i] == sArray[j])
return true;
}
}
return false;
}
最佳答案
不,不是,它是 O(n^2),因为您在外循环中迭代整个数组,并且对于 i
的每个值,您也在迭代整个数组内循环中的数组。将数组分成两部分的事实不会改变顺序复杂性。
如果您想使用 O(n*log(n)) 算法查找重复项,您可以对数组进行排序,并检查相邻位置是否有重复项,如下所示:
public static boolean isDuplicate(String s){
char[] sArray = s.toCharArray();
Arrays.sort(sArray); // O(n*log(n))
for (int i=0; i<sArray.length-1; i++) // O(n)
if (sArray[i]==sArray[i+1])
return true;
return false;
}
更好的是,您可以使用 HashSet
,并在 O(n) 内查找重复项:
public static boolean isDuplicate(String s){
HashSet<Character> alreadySeenChars = new HashSet<Character>();
char[] sArray = s.toCharArray();
for (int i=0; i<sArray.length; i++) { // O(n)
if (alreadySeenChars.contains(sArray[i])) // O(1)
return true;
alreadySeenChars.add(sArray[i]); // O(1)
}
return false;
}
关于java - 查找字符串中的重复项 - 订单复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16908740/