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

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)（因为需要逐项重新分配？）
return 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

您可以通过按索引筛选来节省 seen：

var t1 = [1, 2, 1, 1, 3, 1, 1, 4];
function uniqueList(list) {
    return list.filter(function (value, index, arr) {
        return list.indexOf(value) == index;
    });
}
console.log(t1);
console.log(uniqueList(t1));

Answer 2

我的答案是建立一个新数组。也许是 O(n).

function dedupe(arr) {
    var result = [];
    var seen = {};
    for(let i = 0; i < arr.length; i++) {
        const e = arr[i];
        if (seen[e]) {            
            //skip
        } else {
            seen[e] = true;
            result.push(e);
        }
        
    }
    return result;
}

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

Answer 3

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

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

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

另一种与您的更相似的方法（但可能与 Set 相同，因为我猜它是使用相同的底层结构实现的）是这样的：

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

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

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

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

Time complexity of a de-duping algorithm

javascript

complexity-theory

time-complexity