java 如果数组包含重复的元素(不需要相邻),则返回true

ulydmbyx  于 2023-02-07  发布在  Java
关注(0)|答案(3)|浏览(89)

当我执行这个命令时,即使没有重复的,它也会显示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;
}
vjhs03f7

vjhs03f71#

您正在比较数组偏移量,而不是这些偏移量处的值。
这个

if(i==j)

应该是

if(duplicateArray[i]== duplicateArray[j])

也就是说,你的算法效率很低,至少,一旦检测到重复,你应该中断循环,最简单的方法是立即return true(这样你就不需要same变量了。
一个更有效的方法是对数组进行排序,然后将每个索引与前一个索引进行比较,这样最坏情况下的复杂度是O(nlogn),而不是O(n^2)。

6bc51xsx

6bc51xsx2#

所以,在代码中

if (i==j) {
   same = true;
}

你比较的是归纳,而不是值。你必须跳过比较同一索引的值,如下所示:

if (i==j) {
   continue;
}

if (duplicateArray[i] == duplicateArray[j]) {
    same = true;
    break;
}
cgvd09ve

cgvd09ve3#

正如其他人所说,代码中的问题是比较索引(i and j)而不是值(duplicateArray[i] and duplicateArray[j])。
因此,改变

if (i == j)

if (duplicateArray[i] == duplicateArray[j])

应该能解决你的问题。
但是,为了改进您的解决方案(当前是O(n^2)算法,因为您有两个嵌套循环遍历整个数组),这里有几个方法:
1.找到两个相等元素时返回true
基本上,而不是

same = true;

你就可以

return true;

因为你不关心数组的其他部分你已经找到一对了。
尽管这并没有改善渐进运行时复杂性,但它会通过提前终止来加快代码的速度。
1.预先对数组排序,然后比较相邻元素:
我们可以使用Arrays.sort(duplicateArray);来对数字进行升序排序,只需要O(n log n)的时间,现在,我们保证相等的元素彼此相邻,这意味着我们可以在O(n)的时间之后找到答案。
代码如下所示(收到输入后):

Arrays.sort(duplicateArray);
for (int i = 1; i < duplicateArray.length; i++) {
  if (duplicateArray[i] == duplicateArray[i - 1]) {
    return true;
  }
}
return false;

这将运行时复杂性降低到O(n log n)
1.使用HashSet
HashSet s有一个.contains()方法,该方法在预期的O(1)时间内运行。因此,如果我们将每个已遍历到HashSet中的数字相加,则可以在恒定时间内检查是否相等。因此,遍历数组需要O(n)时间,因此我们可以改进O(n log n)解决方案。
代码如下所示(同样在输入之后):

Set<Integer> set = new HashSet<>();
for (int i = 0; i < duplicateArray.length; i++) {
  if (set.contains(duplicateArray[i])) {
    return true;
  }
  set.add(duplicateArray[i]);
}
return false;

唯一的问题是HashSet会占用额外的空间。

相关问题