如果您的数组嵌套其他数组/对象,使用Set
方法可能不是您想要的,因为比较两个对象会比较它们的引用。如果您想检查它们包含的值是否相等,需要使用其他方法。以下是几种不同的方法。
方法1:使用JSON.stringify
作为键的映射
如果您希望将具有相同包含值的对象视为相等,则可以使用一个简单的方法来使用Map
对象进行操作。它使用JSON.stringify
为数组中的每个元素创建唯一标识符。
我认为这个运行时在数组上的复杂度将是O(n * m),假设JSON.stringify
以线性时间序列化。n是外部数组的长度,m是数组的大小。然而,如果对象变得非常大,这可能会变慢,因为键会变得非常长。这不是一个非常空间有效的实现,但它很简单,并且适用于许多数据类型。
function checkArrayDupeFree(myArray, idFunc) {
const dupeMap = new Map();
for (const el of myArray) {
const id = idFunc(el);
if (dupeMap.has(id))
return false;
dupeMap.set(id, el);
}
return true;
}
const notUnique = [ [1, 2], [1, 3], [1, 2] ];
console.log(`${JSON.stringify(notUnique)} has no duplicates? ${checkArrayDupeFree(notUnique, JSON.stringify)}`);
const unique = [ [2, 1], [1, 3], [1, 2] ];
console.log(`${JSON.stringify(unique)} has no duplicates? ${checkArrayDupeFree(unique, JSON.stringify)}`);
当然,你也可以编写自己的id生成函数,但我不确定你能做得比JSON.stringify
更好。
方法二:自定义HashMap、Hashcode和Equality实现
如果你有很多大数组,从性能上考虑,最好实现自己的哈希/相等函数,并使用Map
作为HashMap。
在以下实现中,我们对数组进行哈希。如果发生冲突,则将一个键映射到一组冲突值,并根据相等函数检查是否有任何数组值匹配。
这种方法的缺点是,你可能需要考虑广泛的类型来制作哈希码/相等函数,具体取决于数组中的内容。
function checkArrayDupeFreeWHashes(myArray, hashFunc, eqFunc) {
const hashMap = new Map();
for (const el of myArray) {
const hash = hashFunc(el);
const hit = hashMap.get(hash);
if (hit == null)
hashMap.set(hash, [el]);
else if (hit.some(v => eqFunc(v, el)))
return false;
else
hit.push(el);
}
return true;
}
这是一个自定义HashMap的演示。我为数组实现了哈希函数和相等性函数。
function checkArrayDupeFreeWHashes(myArray, hashFunc, eqFunc) {
const hashMap = new Map();
for (const el of myArray) {
const hash = hashFunc(el);
const hit = hashMap.get(hash);
if (hit == null)
hashMap.set(hash, [el]);
else if (hit.some(v => eqFunc(v, el)))
return false;
else
hit.push(el);
}
return true;
}
function arrayHasher(arr) {
let hash = 19;
for (let i = 0; i < arr.length; i++) {
const el = arr[i];
const toHash = Array.isArray(el)
? arrayHasher(el)
: el * 23;
hash = hash * 31 + toHash;
}
return hash;
}
function arrayEq(a, b) {
if (a.length != b.length)
return false;
for (let i = 0; i < a.length; i++) {
if ((Array.isArray(a) || Array.isArray(b)) && !arrayEq(a[i], b[i]))
return false;
else if (a[i] !== b[i])
return false;
}
return true;
}
const notUnique = [ [1, 2], [1, 3], [1, 2] ];
const unique = [ [2, 1], [1, 3], [1, 2] ];
console.log(`${JSON.stringify(notUnique)} has no duplicates? ${checkArrayDupeFreeWHashes(notUnique, arrayHasher, arrayEq)}`);
console.log(`${JSON.stringify(unique)} has no duplicates? ${checkArrayDupeFreeWHashes(unique, arrayHasher, arrayEq)}`);
for (var j = i; j < myArray.length; j++)
,因为你已经检查过前面的指数了,所以没有必要再次比较它们的唯一性。 - Richard Dalton