如何在JavaScript中检测元素唯一数组

发布于1/15/2020 来自:「前端知否」微信公众号

当JavaScript数组包含原始值(字符串,数字,未定义,null,布尔值和符号)时,在某些情况下,您可能想检测该数组是否包含任何重复的元素。

换句话说,您将要确定数组中的元素是否唯一。您可以采用几种方法来实现此目的。

方法1.嵌套循环

在这种方法中,我们将从第一个元素开始遍历数组,对于每个元素,我们都将该元素与所有其他元素进行比较,以查看是否存在匹配项。

为此,我们将使用两个嵌套在一起的for循环。

function isUnique(arr) {
const len = arr.length;

for (let i = 0; i < len; i++) {
for (let j = 0; j < len; j++) {
// 如果有元素匹配,则说明数组中的元素不唯一
if (i !== j && arr[i] === arr[j]) {
return false;
}
}
}

return true;
}

尽管此方法在小型和半小型数据集上都可以很好地工作,但是随着输入数据集的增长,它变得越来越慢。这种方法之所以缓慢,是因为存在嵌套循环。

想象一个百万个数字的数据集。在此数据集中,在最坏的情况下,我们重复的元素可能是数组中的最后一个元素,因此,我们需要将一百万个数字与一百万个数字(一百万*一百万)进行比较,这非常慢。

方法2. 具有缓存值的单循环

采用这种方法,我们不会跟踪每个元素,而是跟踪访问的元素,而不是重复元素的匹配项。

换句话说,我们缓存遍历的内容,然后仅查找它们以查找下一个元素,以检查是否已经访问过该元素。

由于有此访问的引用,我们只需要将数组中的每个元素与此引用进行比较,因此,我们只需要遍历此数组一次。

function isUnique(arr) {
const seenValues = {}

for (let i = 0; i < arr.length; i++) {
// 元素已经在缓存中
if (seenValues[arr[i]]) {
return false;
} else {
seenValues[arr[i]] = true
}
}

return true;
}

在数据集中有一百万个数字的最坏情况下,我们重复的元素将是最后一个元素,但是在这种方法中,我们只比较一百万次。此方法比方法1快得多。

方法3.使用ES6 Set

当ES6出现时,我们被引入了JavaScript中称为Sets的新数据结构。

集合是根据定义唯一的元素的集合,这意味着,如果您尝试将重复的元素插入到集合中,则不会产生任何影响。

根据定义,由于集是唯一元素的集合,因此存在一种将数组转换为集的技术,进而可以将数组中的项目唯一集合,现在存储在集合中。

然后,将使用反向操作将该Set转换回数组。从某种意义上讲,您可以说Set用作中间数据结构以从数组中删除重复的元素。

Array -> Set -> Array

/* 转换数组为Set,然后再转换回来 */
function getUniqueArray(arr) {
return [...new Set(arr)]
}

function isUnique(arr) {
return getUniqueArray(arr).length === arr.length
}

在这种方法中,如果唯一数组(从Set转换回来)中的元素数与输入数组的长度相同,则意味着此数组已经包含唯一值,并且没有重复的值被删除以改变长度。

注意:如果您只想检查唯一性,则无需将Set转换回数组。您可以通过检查Set.prototype.size完全跳过此部分操作。

/* 转换数组为Set */
function arrayToSet(arr) {
return new Set(arr)
}

function isUnique(arr) {
return arrayToSet(arr).size === arr.length
}

性能比较

只要您的数据集相对较小,就可以交替使用这三种方法中的任何一种。对于较大的数据集,您需要关注这些方法的性能以及它们在有限的时间内可以执行多少次操作。

这三个之间的性能比较的简短答案是:

方法2>方法3>方法1。

方法2(使用具有缓存值的单循环)比其他方法快得多。在方法3(设置)和方法1(嵌套循环)之间,方法3也快得多

最后

  • 方法1(使用嵌套循环)具有二次复杂度,这意味着将导致O(n2)时间复杂度。
  • 方法2(使用单循环和缓存的值)具有线性复杂度,这意味着它将导致O(n)时间复杂度。
  • 对于方法3,我没有强烈的意见,因为我不完全了解如何在后台的JavaScript引擎中实现Set。