java - 配列リストで重複する要素のインデックスを見つける

Question

文字列の配列リストで重複のインデックス位置を見つけようとしています。arraylist を効率的にループして重複のインデックスを報告する方法を見つけるのに苦労しています。私の最初の考えは、Collections.binarySearch() を使用して重複を探すことでしたが、arraylist の要素を 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

今、これはメモリ効率の良い解決策ではないかもしれませんが、はい、これはあなたが探していたものだと思います..このプログラムはさらに改善される可能性があります.

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 3

運が悪いようですね。

すべての要素を検査する必要があります (つまり、リスト全体を反復処理します)。論理的に考えてみてください。これを回避できた場合、まだ検査していない要素が 1 つあります。ただし、この要素は任意の値である可能性があるため、別のリスト要素の複製である可能性があります。

二分探索は、リスト全体に保持される何らかの関係を認識している場合に、チェックする要素の数を減らす賢い方法です。そのため、1 つの要素をチェックすると、他の要素に関する情報が得られます。たとえば、並べ替えられたリストの場合、中央の要素が 5 より大きい場合、それ以降のすべての要素も 5 より大きいことがわかります。

ただし、重複チェックに関しては、そのような推論を行う方法はないと思います。「これが重複している要素の数」（これは疑問を投げかけています）の観点からリストをソートする必要があります。そうしないと、要素に対して実行するテストでは、重複xしているかどうかについての洞察が得られません。y