javascript - 重复数据删除算法的时间复杂度

Question

这是一个从数组中删除重复项的函数。

function dedupe(arr) {
    var seen = {};
    arr.forEach((e,i)=>{
        if (seen[e]) {
            arr.splice(i, 1);
        }
        seen[e] = true;
    });
    return arr;
}

console.log(dedupe([1, 2, 1, 3, 4]));

我对这个函数的时间复杂度很感兴趣。

如果我们假设 Array 由一个真正的数组支持，那么时间复杂度是否可以分析如下？

• seen 的分配:O(1)
• 枚举所有元素:O(n)
• 删除重复项:O(n)(因为需要逐项重新分配？)
• 返回 O(1)

那么这是一个 O(n^2) 算法吗？

编辑:

更正了索引问题。

function dedupe(arr) {
    var seen = {};
    for(let i = 0; i < arr.length; i++) {
        const e = arr[i];
        if (seen[e]) {            
            arr.splice(i, 1);
            i--; // we have modified the array and need to continue from the current index
        }
        seen[e] = true;
    }
    return arr;
}

console.log(dedupe([1, 2, 1, 3, 1, 4, 4, 7, 6, 7, 7, 7, 1, 5]));

对于那些对上述表现感到不安的人，我认为这是 O(N)。

我想就地删除重复数据。使用 Set 维护跨主机环境的顺序。

function dedupe(arr) {
    var seen = new Set();
    for(let i = 0; i < arr.length; i++) {
        seen.add(arr[i]);
    }
    arr.length = 0; // empty the array
    return arr.concat(...seen.keys());
}

console.log(dedupe([1, 2, 1, 3, 1, 4, 4, 7, 6, 7, 7, 7, 1, 5]));

Answer 1

一种方法是使用 Javascript Set .你可以简单地这样做:

const removeDuplicates = array => (new Set(array)).values()

这将返回一个迭代器，而不是一个数组，但是这很容易修复。此外，大多数浏览器还不支持集合。这个的复杂度应该是O(n)。

另一种与您的方法更相似的方法(但可能与 Set 相同，因为我猜它是使用相同的底层结构实现的)如下所示:

const removeDuplicates = array =>
    Object.keys(array.reduce((agg, x) => { agg[x] = true; return agg }, {}))

这个的时间复杂度应该是 O(m+n)，其中 m 是唯一项的数量，它总是 <= n，因此是 O(n)。

此外，您计算出的时间复杂度似乎是正确的。