java - 在arraylist中查找重复元素的索引

Question

我试图在字符串数组列表中找到重复项的索引位置。我无法找到一种有效循环遍历数组列表并报告重复索引的方法。我最初的想法是使用 Collections.binarySearch() 来查找重复项，但我不确定如何使用 binarySearch 将数组列表的元素相互比较。我唯一的另一个想法是遍历列表，这非常庞大，次数太多甚至都不可行。我的Java知识有限，因此不胜感激。

Answer 1

不优雅，但应该工作：

Map<String, List<Integer>> indexList = new HashMap<String, List<Integer>>();
for (int i = 0; i < yourList.size(); i++) {
    String currentString = yourList.get(i);
    List<String> indexes = indexList.get(currentString);
    if (indexes == null) {
         indexList.put(currentString, indexes = new LinkedList<Integer>());
    }
    indexes.add(i);
    if (indexes.size() > 1) {
        // found duplicate, do what you like
    }
}
// if you skip the last if in the for loop you can do this:
for (String string : indexList.keySet()) {
    if (indexList.get(string).size() > 1) {
        // String string has multiple occurences
        // List of corresponding indexes:
        List<Integer> indexes = indexList.get(string);
        // do what you want
    }
}

Answer 2

听起来你运气不好。

您将不得不检查每个元素（即遍历整个列表）。从逻辑上考虑 - 如果你能避免这种情况，这意味着你没有检查过一个元素。但是这个元素可以是任何值，因此可以是另一个列表元素的副本。

当您知道列表中存在某种关系时，二分搜索是一种减少检查元素数量的聪明方法 - 因此检查一个元素可以为您提供有关其他元素的信息。例如，对于一个排序列表，如果中间元素大于 5，则您知道它后面的每个元素也都大于 5。

但是，我认为在重复检查方面没有办法做出这样的推断。您必须根据“此重复的元素数量”（这是在回避问题）对列表进行排序，否则您对元素执行的任何测试都不x会让您深入了解是否y是重复的。

Answer 3

现在这可能不是一个内存有效的解决方案，但是是的，我想这就是你想要的。也许这个程序可以进一步改进。

import java.io.*;
import java.util.*;

class ArrayList2_CountingDuplicates
{
public static void main(String[] args)throws IOException
{

ArrayList<String> als1=new ArrayList<String>();
ArrayList<String> als2=new ArrayList<String>();
int arr[];
int n,i,j,c=0;
String s;

BufferedReader p=new BufferedReader(new InputStreamReader(System.in));

n=Integer.parseInt(p.readLine());

arr=new int[n];

for(i=0;i<n;i++)
als1.add(p.readLine());

for(i=0;i<n;i++)
{

s=als1.get(i);
als1.remove(i);
als2.add(s);

arr[c]=1;

while(als1.contains(s))
{
j=als1.indexOf(s);
als1.remove(j);
arr[c]=arr[c]+1;
}
n=n-arr[c];
c=c+1;
i=-1;
}

    for(i=0;i<c;i++)
    System.out.println(als2.get(i)+" has frequency  "+arr[i]);
    }

}

Answer 4

我一直在寻找这样的方法，最终我想出了我自己的解决方案，用一种更实用的方法来解决这个问题。

public <T> Map<T, List<Integer>> findDuplicatesWithIndexes(List<T> elems) {
    return IntStream.range(0, elems.size())
            .boxed()
            .collect(Collectors.groupingBy(elems::get))
            .entrySet().stream()
            .filter(e -> e.getValue().size() > 1)
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));
}

它返回一个由重复元素组成的映射作为键和重复元素的所有索引的列表作为值。