从数组中删除重复项的程序不会删除某些项

问题描述：

我已经编写了以下短程序，提示用户构造一个整数ArrayList，然后显示删除了重复项的同一个数组。该程序可以很好地处理简单的数字，例如1,10甚至100个。请注意，排序不在此程序中，因为我只为自己编写排序。不过，我确实明白没有将程序分类的含义。从数组中删除重复项的程序不会删除某些项

略大的数字不能被正确检测为重复。例如，如果我选择构造一个具有两个整数的数组，两个数值均为700，则该方法不会删除重复项。是否有其他一些我不明白的概念，或者是我忽略的代码中的一个小错误？

import java.util.*; 

public class DuplicateArray 
{ 

    public static void main(String [] args) 
    { 

     // Variables 
     Scanner scan = new Scanner(System.in); 


     // Prompt user and create an array 
     System.out.print("\nHow many items will your array contain: "); 
     int size = scan.nextInt(); 
     ArrayList<Integer> numbers = new ArrayList<Integer>(size); 


     // Construct the array 
     for(int i = 0; i < size; i++) 
     { 
      System.out.print("Item #" + (i+1) + ": "); 
      numbers.add(scan.nextInt()); 
     } 


     // Remove duplicates 
     compress(numbers); 


     // Print compressed array 
     System.out.println("\nBelow is that same array with duplicates removed."); 
     for(int i = 0; i <= numbers.size()-1; i++) 
     { 
      System.out.print(numbers.get(i) + " "); 
     } 


    } 




    /* 
    * Removes duplicates from the input array 
    */ 
    public static void compress(ArrayList<Integer> numbers) 
    { 

     // If the array is of size 1, then there are no duplicates to check for */ 
     if(numbers.size() <= 1) 
     { 
      return; 
     } 

     // Traverse the array backwards */ 
     for(int i = numbers.size() - 1; i > 0; i--) 
     {   
      if(numbers.get(i) == numbers.get(i-1)) 
      { 
       numbers.remove(i); 
      } 
     } 
    } 

}

我会使用'LinkedHashSet'（如果你需要保留插入顺序）或者一个常规'HashSet'（如果你不这样做）。 –

我还没有知道。我的代码中是否有逻辑错误？ – AleksandrH

如果您对'List'进行排序，则您的方法将仅工作（按原样）。 –

答

使用比较没有这个 numbers.get(i) == numbers.get(i-1)但numbers.get(i).equals(numbers.get(i-1))方法。

这种奇怪行为的原因是内部JVM具有从-128..127（参见Integer#valueOf方法实现）的Integer值的缓存。因此numbers.get(i) == numbers.get(i-1)只适用于这个数字范围。但对于不在范围内的数字，这种比较操作不起作用，您必须使用equals方法。

我根据您的建议修改了我的代码，并按预期工作。你能否请解释_why_解决问题？ – AleksandrH

@AleksandrH刚更新我的答案和我的解释 –

有趣！我不知道。只需用两个项目127 127和128 128重新执行该程序，它确实表现得那样。多么奇怪。 – AleksandrH

答

你的压缩函数有很多潜在的问题。

主要问题是您只比较位置i的数字和位置i-1的数字。由于您没有提前排序您的数组，因此您不能保证重复数字的位置会彼此相邻。

解决方法是先对数组进行排序，然后运行代码。合并或快速排序将使您的nlog（n）复杂性。

或者你可以运行一个嵌套for循环，检查每个数字与整个列表中寻找重复。请记住，这确实将O时间复杂度提高到O（n^2）。

从数组中删除重复项的程序不会删除某些项

相关推荐