在多维 javascript 数组中查找唯一条目，重要顺序取决于级别

Question

在多维 javascript 数组中找到所有唯一的第一级条目的最优雅的解决方案是什么？只有一个重要的规则：条目的顺序只在第一层重要，但在第二层不重要

例如，对于以下数组，脚本应该 return 4 个唯一条目（第一个、第三个、第四个和第五个）：

[
  [ [],[22],[1,13,17],[12],[] ], 
  [ [],[22],[17,13,1],[12],[] ], 
  [ [],[12],[1,13,17],[22],[] ], 
  [ [11],[12],[13],[14],[15] ], 
  [ [15],[14],[13],[12],[11] ]
]

PS。 jQuery 也可以使用。

Answer 1

首先，这里有一个可以使用的 JSFiddle：http://jsfiddle.net/missyalyssi/ro8o94nk/

给定一个输入数组，函数 findUnique 将 return 一个包含根据您的定义唯一的项目的数组。所以，例如：

[[8],[1,2,3],[9]] 是 [[8], [3,1,2], [9]] 的副本，但不是[[9], [3,1,2], [8]]

我写这篇文章的主要目的是让它易于阅读和理解。

function findUnique(input) {
  let found = [];
  let uniqueEls = new Set();
  let hasDup = true;
  for (let element of input) {
    hasDup = found.length && 
             found.every((el) => {return deepEqualsNaive(el, element)});
    if (hasDup) {
      uniqueEls.delete(element);
      continue;
    }
    found.push(element);
    uniqueEls.add(element);
  }
  return [...uniqueEls];
}

该函数使用deepEqualsNaive判断两个数组是否相等。由于 javascript 中的对象相等意味着数组将指向相同的内存位置，因此我们需要构建自己的函数以 return 为真，即我们所说的相等。在这里，“相等”是指它们具有相同的元素，即使它们没有指向相同的内存位置或以相同的顺序出现。

为了可读性，我递归地编写了这个函数我不知道你在其中使用它的上下文。如果你可以溢出堆栈，那么使用迭代版本。

以下是一些示例输入以及我们的预期：

deepEqualsNaive([ [],[22],[1,13,17],[12],[] ], [ [],[22],[17,13,1],[12],[] ]) => true

deepEqualsNaive([ [],[22],[17,13,1],[12],[] ], [ [],[12],[1,13,17],[22],[] ]) => false

deepEqualsNaive([ [],[22],[1,13,17],[12],[] ], [ [],22,[17,13,1],[12],[] ]) => false

函数：

function deepEqualsNaive (input, clone) {
  if (!Array.isArray(input) || !Array.isArray(clone)) return false;
  if (input.length !== clone.length) return false;
  var result = 0;
  for (let elIdx = 0; elIdx < input.length; elIdx++) {
    var tryDeep = true;
    if (Array.isArray(input[elIdx])) tryDeep = deepEqualsNaive(input[elIdx], clone[elIdx]);
    if (!tryDeep) return false;
    result ^= input[elIdx];
    result ^= clone[elIdx];
  }
  return result === 0;
}

Answer 2

如果可以引用原始数组 'records' 和内部数组（即没有深拷贝），您可以使用类似的东西：

function distinct(arr){
    const res =[], //array with results
     cmpArr = (a1,a2) => a1.length===a2.length && a1.every((i,ind) => a2[ind] === i),
     cmpRec = (a1,a2) => [1,2,3].every(i=> cmpArr(a1[i],a2[i])); //compare 'records' for indices 1,2 and 3    
  for(let subarr of arr){   
    subarr[2].sort(); //NB, this alters the source array. If this is not allowed, a work around can be created
    if(!res.some(r => cmpRec(r,subarr))) //check if 'res' doesn't have an entry , based on the cmpRec function
     res.push(subarr);      
  }
  return res;
}

//test:
let input = [
  [ [],[22],[1,13,17],[12],[] ], 
  [ [],[22],[17,13,1],[12],[] ], 
  [ [],[12],[1,13,17],[22],[] ], 
  [ [11],[12],[13],[14],[15] ], 
  [ [15],[14],[13],[12],[11] ]
];

console.log(distinct(input).map(JSON.stringify));

Answer 3

如果您不是那么担心性能并且只需要一些有用的东西，您可以使用您提到的恒定深度以及字符串表示形式作为 "fingerprint" 种类（类似于 Java的hashcode).

然后您使用 Set 来跟踪您以前没有见过的项目，并且只添加新的项目。

function getUnique(rows) {
  let unique = new Set();
  let results = [];
  for (let row of rows) {
    // Fingerprint is the string representation of the row,
    // with the inner-level sorted (as order doesn't matter).
    // E.g., fingerprint of [ [8], [3, 2, 1], [9] ] is '[[8],[1,2,3],[9]]'
    let fingerprint = JSON.stringify(row.map((cells) => {
      return cells.concat().sort();  // Use concat to avoid sorting in place.
    }));

    // If we haven't seen this fingerprint before,
    // add to the filter and the results list.
    if (!unique.has(fingerprint)) {
      unique.add(fingerprint);
      results.push(row);
    }
  }
  return results;
}

例如，这将得出...

> x = [
... [ [8], [3, 2, 1], [9] ],
... [ [7], [8, 3, 9], [1, 2] ],
... [ [8], [1, 2, 3], [9] ],
... ];
> getUnique(x);
[ [ [ 8 ], [ 3, 2, 1 ], [ 9 ] ],
  [ [ 7 ], [ 8, 3, 9 ], [ 1, 2 ] ] ]

显然，如果您的内在值是 non-primitives（对象、数组等），那么这将失败，但如果您像您的示例一样处理数字，应该没问题。

在多维 javascript 数组中查找唯一条目，重要顺序取决于级别

find unique entries inside a multidimensional javascript array, order important dependent on level

javascript

arrays

jquery

unique

multidimensional-array