Java - 删除ArrayList中的重复项

Question

我正在研究一个使用ArrayList存储的程序Strings.程序通过菜单提示用户,并允许用户选择要执行的操作.这样的操作是将字符串添加到列表,打印条目等.我想要做的是创建一个名为的方法removeDuplicates().此方法将搜索ArrayList并删除任何重复的值.我想在列表中留下一个重复值的实例.我还希望此方法返回已删除的重复项的总数.

我一直在尝试使用嵌套循环来实现这一点,但是我遇到了麻烦,因为当条目被删除时,变量的索引ArrayList会被改变,并且事情不能正常工作.我从概念上知道我需要做什么但是我在代码中实现这个想法时遇到了麻烦.

这是一些伪代码:

从第一次入门开始; 检查列表中的每个后续条目,看它是否与第一个条目匹配; 删除列表中与第一个条目匹配的每个后续条目;

在检查完所有条目后,转到第二个条目; 检查列表中的每个条目,看它是否与第二个条目匹配; 删除列表中与第二个条目匹配的每个条目;

重复列表中的条目

这是我到目前为止的代码:

public int removeDuplicates()
{
  int duplicates = 0;

  for ( int i = 0; i < strings.size(); i++ )
  {
     for ( int j = 0; j < strings.size(); j++ )
     {
        if ( i == j )
        {
          // i & j refer to same entry so do nothing
        }

        else if ( strings.get( j ).equals( strings.get( i ) ) )
        {
           strings.remove( j );
           duplicates++;
        }
     }
 }

   return duplicates;
}

更新:似乎Will正在寻找一个家庭作业解决方案,其中涉及开发算法以删除重复项,而不是使用集合的实用解决方案.看他的评论:

谢谢你的建议.这是作业的一部分,我相信老师原本打算让解决方案不包括作品集.换句话说,我想出一个解决方案,搜索和删除重复项而不实现HashSet.老师建议使用嵌套循环,这是我正在尝试做的但是我已经遇到了一些问题,ArrayList删除了某些条目之后的索引.

Answer 1

为什么不使用像Set(和类似的实现HashSet)这样的集合来自然地防止重复？

Answer 2

您可以使用嵌套循环而不会出现任何问题:

public static int removeDuplicates(ArrayList<String> strings) {

    int size = strings.size();
    int duplicates = 0;

    // not using a method in the check also speeds up the execution
    // also i must be less that size-1 so that j doesn't
    // throw IndexOutOfBoundsException
    for (int i = 0; i < size - 1; i++) {
        // start from the next item after strings[i]
        // since the ones before are checked
        for (int j = i + 1; j < size; j++) {
            // no need for if ( i == j ) here
            if (!strings.get(j).equals(strings.get(i)))
                continue;
            duplicates++;
            strings.remove(j);
            // decrease j because the array got re-indexed
            j--;
            // decrease the size of the array
            size--;
        } // for j
    } // for i

    return duplicates;

}

Answer 3

您可以尝试使用此一个班轮来获取字符串保留顺序的副本.

List<String> list;
List<String> dedupped = new ArrayList<String>(new LinkedHashSet<String>(list));

这种方法也是O(n)摊销而不是O(n ^ 2)

Answer 4

只是为了澄清我对matt b答案的评论,如果你真的想要计算删除的重复数量,请使用以下代码:

List<String> list = new ArrayList<String>();

// list gets populated from user input...

Set<String> set = new HashSet<String>(list);
int numDuplicates = list.size() - set.size();