在数组中查找重复的数组

Question

假设有一个数组，其中包含多个子数组，如何高效地识别重复元素？

var array = [
  [
    11.31866455078125,
    44.53836644772605
  ],
  [                     // <-- Here's the duplicate
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.50140292110874
  ]
]

我一直在使用已经被接受的依赖项 lodash 进行相关的 IT 技术工作，并且我知道如何仅使用 _.uniqWith 和 _.isEqual 来返回“唯一”列表：

_.uniqWith(array,_.isEqual)

这将给出“唯一”的列表版本：

[ 
    [ 11.31866455078125,  44.53836644772605 ],
    [ 11.371536254882812, 44.53836644772605 ],
    [ 11.371536254882812, 44.50140292110874 ]
]

不仅要报告唯一元素，我需要的是重复元素，最好是第一个出现的索引。

这个问题是否已经被lodash库中的某些方法涵盖？或者说我必须写循环来比较元素？

如果有适合的库方法，我会尽量避免重写函数，所以我基本上陷入了困境：

1. 只返回重复项或至少与“唯一列表”的比较差异。

2. 基本上确定数组中数组的“索引”。虽然一旦确定了重复项，可以使用_.isEqual进行过滤缩减。

也尝试避免创建对象哈希/映射并在此处计算键的发生次数，或者至少不作为单独的对象，而是作为可以“内联”功能化的东西。

- Neil Lunn

Answer 1

Lodash提供了许多有用的函数来实现查找第一个重复索引。
使用_.findIndex()和_.isEqual()，以下代码将找到第一个重复索引：

var duplicateIndex = _.findIndex(array, function(value, index, collection) {
  var equal = _.isEqual.bind(undefined, value);
  return _.findIndex(collection.slice(0, index), equal) !== -1;
});

或者稍微快一点但更加冗长：

var duplicateIndex = _.findIndex(array, function(value, index, collection) {
  var equal = _.isEqual.bind(undefined, value);
  return _.findIndex(collection, function(val, ind) {
     return ind < index && equal(val);
  }) !== -1;
});

注意，如果没有重复项，则返回-1。
这个算法会遍历整个数组并查看当前元素是否已经存在。如果存在，就返回当前迭代的索引。
请检查工作演示。

- Dmitri Pavlutin

---

进一步查看后，我发现了我的笔误，并仔细查看了代码，明白了你在这里做什么。不能说我对使用.slice()来不断扩展列表感到非常满意，但它确实比仅使用索引循环更加简洁。正在考虑中。 - Neil Lunn

@NeilLunn _.findIndex(collection.slice(0, index), equal) !== -1; 可以简化为手动的 findIndex，只需迭代一次即可。但当前的方法是紧凑的。 - Dmitri Pavlutin

我也是这么想的。不过你已经得到了我的投票。我还在整理思路，考虑各种选择。就像我说的，这种方法编码更加简洁，比其他方法更好。 - Neil Lunn

Answer 2

你可以使用纯JavaScript来实现，这并不难，这是我的实现方式。

for (let i = 0; i < array.length; i++) {
  for (let j = i + 1; j < array.length; j++) {
  
     // quick elimination by comparing sub-array lengths
     if (array[i].length !== array[j].length) {
        continue;
     }
     // look for dupes
     var dupe = true;
     for (var k = 0; k < array[i].length; k++) {
       if (array[i][k] !== array[j][k]) {
         dupe = false;
         break;
       }
     }
     // if a dupe then print
     if (dupe) {
         console.debug("%d is a dupe", j); 
     }
   }
 }

这种实现的优点在于，它可以打印出多个重复项，你可以利用这个事实来计算每个索引中的重复项数量！

实际上，这是一种非常有效的方法，因为内部的 for 循环（j）总是从外部循环（i）的下一个位置开始运行。所以您可以减少一半的检查次数。

这里提供了一个示例链接：plunk

- svarog

Answer 3

下面是一种使用 uniqWith() 和 difference() 的方法：

_.indexOf(array, _.head(_.difference(array, _.uniqWith(array, _.isEqual))));

基本思路是：

1. 使用 uniqWith() 从 array 中去除重复项。
2. 使用 difference() 将 array 与无重复项的版本进行比较，得到一个包含重复项的数组。
3. 使用 head() 获取数组的第一项，这就是我们感兴趣的重复项。
4. 使用 indexOf() 找到重复项的索引，在本例中为 1。

然而，如果您需要的是原始数据的索引而不是它的重复项，我们需要做出一些调整：

var duplicate = _.head(_.difference(array, _.uniqWith(array, _.isEqual)));
_.findIndex(array, _.unary(_.partial(_.isEqual, duplicate)));

我们仍然使用 uniqWith() 和 difference() 来查找 duplicate。但现在，我们使用 findIndex() 来获取索引。原因是我们需要使用 isEqual() 找到重复项的 第一个 位置，而不是 第二个。我们使用 partial() 和 unary() 构建谓词。这次的结果是 0。

- Adam Boduch

---

我发誓这是我尝试的第一件事情，因为它在逻辑上很有道理。但我想我的大脑开始使用_.differenceWith()和相同的_.isEqual，而只需要一个纯粹的_.difference()。过度思考可能就会被排除掉。索引匹配的方法也很不错。 - Neil Lunn

Answer 4

我相信构建查找表是进行比较的最有效方法之一。以下方法利用Array.prototype.reduce()构建查找表，并最终通过删除所有重复元素（无论有多少个）来改变原始数组。

var arr = [
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.31866455078125,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.53836644772605
  ],
  [
    11.371536254882812,
    44.50140292110874
  ]
];
arr.reduce((p,c,i)=> { var prop = c[0]+"" + c[1]+"";
                       p[prop] === void 0 ? p[prop] = i : p.dups.push(i);
                       return p;
                     },{dups:[]}).dups.reverse().forEach( i => arr.splice(i,1))

document.write('<pre>' + JSON.stringify(arr, 0, 2) + '</pre>');

然而，如果您想通过保留原始数组来创建一个新的数组，那么显然这将是一个更快的过程。

- Redu

Answer 5

除了自己编写算法，我不知道如何完成这个任务。这个答案和其他发布的答案都不是非常高效，但应该可以胜任：

function findIndex(array, startingIndex, value) {
  var predicate = _.partial(_.isEqual, value);
  var arraySubset = array.slice(startingIndex+1);
  var index = arraySubset.findIndex(predicate);
  return index === -1 ? index : index+startingIndex+1;
}

function findDuplicates(array) {
  return array.map((value, index) => {
    return {
      value,
      index: findIndex(array, index, value)
    };
  }).filter(info => info.index !== -1);
}

findDuplicates([1, 2, 3, 4, 1, [ 3 ], [ 4 ], [ 3 ] ]);

// [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ]    // [ { value: 1, index: 4 }, { value: [ 3 ], index: 7 } ]

这基本上创建了一个数组的映射，对数组的其余部分调用.findIndex（），记录任何重复项的索引，返回每个具有重复项及其重复项索引的项目的信息。

其中一个好处是它可以处理三重复制品或任何值的任何数量的出现。

- Alan