JavaScriptで連想配列の配列の中で重複している行を取得したい

Question

連想配列の配列の中で重複している行を取得しユーザーに通知したいです。
重複条件としては全てのプロパティが同じ場合です
データ量が最大１万件ほどになりそうなのでできるだけ早い処理をしたいと思っています。
ただ現状filter関数でループするしか思い付かずデータ量の２乗のループになってしまうため処理が遅いことが課題です。

※重複している行数の取得が難しければ重複を削除した配列を作りたいです。

何か良い方法ありましたらご教示願いたいです。

例）

[
{id:1, name: 'a', type: 'a'}
{id:2, name: 'b', type: 'b'}
{id:3, name: 'c', type: 'c'}
{id:1, name: 'a', type: 'a'}
{id:4, name: 'd', type: 'd'}
{id:1, name: 'a', type: 'b'}
]

→　１行目と４行目が重複しています

Comments

[int32_t]

結果の行数は、この入力の配列のインデックスでなければならないですか? 入力の配列をソートして、ソート後のインデックスでもokですか?

[taihe-]

ソート前のインデックスが良いです。

Answer 1

配列要素を順に見ながら、「要素の内容で一意になるキー : 出現インデックスのリスト」というマップを作って、そのマップのインデックスのリストの長さが２以上になるものを出力すれば、O(N) ですね。

const array = [
  {id:1, name: 'a', type: 'a'},
  {id:2, name: 'b', type: 'b'},
  {id:3, name: 'c', type: 'c'},
  {id:1, name: 'a', type: 'a'},
  {id:4, name: 'd', type: 'd'},
  {id:1, name: 'a', type: 'b'},
];

function stringify(entry) {
  return `id:${entry.id}, name:'${entry.name}', type:'${entry.type}'`;
}

function logDuplicates(a) {
  const map = new Map();
  a.forEach((entry, index) => {
    const key = stringify(entry);
    const dups = map.get(key);
    if (!dups)
      map.set(key, [index]);
    else
      dups.push(index);
  });
  for (let dups of map.values()) {
    if (dups.length > 1)
      console.log(dups.map(i => `${i + 1}`).join('行目と') + '行目が重複しています');
  }
}
logDuplicates(array);

Answer 2

重複を削除した配列です。

console.log ([...(new Map (ary.map (a=> [Object.values(a).join('|'), a]))).values()]);
//重複するもの取得
console.log(ary.reduce (([a,b],c,d)=>(b.has (d=Object.values(c).join('|'))? [[...a,c],b]: [a,b.add(d)]) ,[[],new Set])[0]);

Answer 3

冗長に

var a=[
{id:1, name: 'a', type: 'a'},
{id:2, name: 'b', type: 'b'},
{id:3, name: 'c', type: 'c'},
{id:1, name: 'a', type: 'a'},
{id:4, name: 'd', type: 'd'},
{id:1, name: 'a', type: 'b'},
];
for(var i=0;i<a.length-1;i++){
  for(var j=i+1;j<a.length;j++){
    if(JSON.stringify(a[i])==JSON.stringify(a[j])){
      console.log([i+1,j+1]);
    }
  }
}