当我执行这个命令时,即使没有重复的,它也会显示true。基本上,我放入的每个数组都显示true。我不知道为什么它会显示这个。我希望在这个问题上得到一些帮助!谢谢!
public static boolean Duplicate()
{
int [] duplicateArray = new int[5];
System.out.print("Enter your array numbers:");
System.out.println();
for(int i = 0; i < duplicateArray.length; i++)
{
Scanner in = new Scanner(System.in);
duplicateArray[i] = in.nextInt();
}
boolean same = false;
for(int i = 0; i < duplicateArray.length-1; i++)
{
for(int j = 0; j < duplicateArray.length; j++)
{
if(i==j)
{
same = true;
}
}
}
return same;
}
3条答案
按热度按时间vjhs03f71#
您正在比较数组偏移量,而不是这些偏移量处的值。
这个
应该是
也就是说,你的算法效率很低,至少,一旦检测到重复,你应该中断循环,最简单的方法是立即
return true
(这样你就不需要same
变量了。一个更有效的方法是对数组进行排序,然后将每个索引与前一个索引进行比较,这样最坏情况下的复杂度是O(nlogn),而不是O(n^2)。
6bc51xsx2#
所以,在代码中
你比较的是归纳,而不是值。你必须跳过比较同一索引的值,如下所示:
cgvd09ve3#
正如其他人所说,代码中的问题是比较索引(
i and j
)而不是值(duplicateArray[i] and duplicateArray[j]
)。因此,改变
到
应该能解决你的问题。
但是,为了改进您的解决方案(当前是
O(n^2)
算法,因为您有两个嵌套循环遍历整个数组),这里有几个方法:1.找到两个相等元素时返回
true
:基本上,而不是
你就可以
因为你不关心数组的其他部分你已经找到一对了。
尽管这并没有改善渐进运行时复杂性,但它会通过提前终止来加快代码的速度。
1.预先对数组排序,然后比较相邻元素:
我们可以使用
Arrays.sort(duplicateArray);
来对数字进行升序排序,只需要O(n log n)
的时间,现在,我们保证相等的元素彼此相邻,这意味着我们可以在O(n)
的时间之后找到答案。代码如下所示(收到输入后):
这将运行时复杂性降低到
O(n log n)
1.使用
HashSet
:HashSet
s有一个.contains()
方法,该方法在预期的O(1)
时间内运行。因此,如果我们将每个已遍历到HashSet
中的数字相加,则可以在恒定时间内检查是否相等。因此,遍历数组需要O(n)
时间,因此我们可以改进O(n log n)
解决方案。代码如下所示(同样在输入之后):
唯一的问题是
HashSet
会占用额外的空间。