在数组中查找重复数组

Question

给定一个数组数组，识别重复项的有效方法是什么？

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

我一直在与 lodash as an accepted dependency, and I get how to just return the "unique" list using _.uniqWith and _.isEqual 合作：

_.uniqWith(array,_.isEqual)

With 会给出列表的 "unique" 版本：

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

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

lodash 库中是否真的包含了我所缺少的一些方法组合？还是我将不得不忍受编写循环来比较元素。

可能只是对此感到过度疲劳，所以欢迎对这个问题有新的看法。

如果有适合的库方法，尽量不要重写函数，所以我基本上坚持：

仅返回副本或至少返回与 "unique list" 的比较差异。
基本上识别"index of"数组中的数组。虽然我认为一旦识别出重复项，就可以使用 _.isEqual 进行过滤减少。

还尝试避免创建对象 Hash/Map 并在此处计算键的出现次数，或者至少不作为单独的对象，并且作为可以在功能上完成的事情 "in-line"。

Answer 1

Lodash 提供了很多有用的函数来实现查找第一个重复索引。
使用 _.findIndex() and _.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 将被 return 编辑。
简而言之，该算法遍历数组并回头查看当前元素是否不存在。如果是，则 return 当前迭代索引。
请检查工作 demo.

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

Answer 3

除了自己编写算法外，我不知道该怎么做。这个答案和其他发布的答案都不是很有效，但应该没问题：

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()，记下任何重复项的索引，返回有关每个具有重复项的信息以及重复项的索引是什么是。

这样做的一个好处是它适用于一式三份或任意数量的值。

Answer 4

这是一种使用 uniqWith(), and difference():

的方法

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

基本思路是：

使用 uniqWith() 从 array 中删除重复项。
使用difference()将array与无重复版本进行比较。这为我们提供了一组重复项。
使用head()获取数组的第一项。这是我们感兴趣的副本。
使用 indexOf() 查找副本的索引，在本例中为 1。

但是，如果您需要原始的索引，而不是重复的，我们必须做一些调整：

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

我们仍在使用 uniqWith() 和 difference() 来查找 duplicate。但是现在，我们正在使用 findIndex() to get the index. The reason is that we need to use isEqual() to find the first position of the duplicate, not the second. We construct the predicate using partial() and unary()。这次的结果是0.

Answer 5

我认为构建 LUT 是进行比较时最有效的方法之一。以下方法通过利用 Array.prototype.reduce() 构造一个 LUT，并最终通过不仅删除一个而且删除所有重复元素（无论有多少）来改变原始数组。

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>');

但是，如果您想通过保留原始数组来获得一个新数组，那么显然这会更快。

在数组中查找重复数组

Find Duplicate Array within Array

javascript

arrays

underscore.js

lodash