set删除⼀个元素时间复杂度_详解使⽤Set来提⾼JS代码性能
的⽅法
我确信有很多开发⼈员坚持使⽤基本的全局对象：数字，字符串，对象，数组和布尔值。对于许多⽤例，这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展，那么这些基本类型并不总是⾜够好。
在本⽂中，我们将讨论JS 中Set对象如何让代码更快— 特别扩展性⽅便。 Array 和Set⼯作⽅式存在⼤量的交叉。但是使⽤Set会⽐Array 在代码运⾏速度更有优势。
Set 有何不同
最根本的区别是数组是⼀个索引集合，这说明数组中的数据值按索引排序。const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2
相⽐之下，set是⼀个键的集合。set不使⽤索引，⽽是使⽤键对数据排序。set 中的元素按插⼊顺序是可迭代的，它不能包含任何重复的数据。换句话说，set中的每⼀项都必须是惟⼀的。
主要的好处是什么
set 相对于数组有⼏个优势，特别是在运⾏时间⽅⾯：查看元素：使⽤indexOf()或includes()检查数组中的项是否存在是⽐较慢的。
删除元素：在Set中，可以根据每项的的 value 来删除该项。在数组中，等价的⽅法是使⽤基于元素的索引的splice()。与前⼀点⼀样，依赖于索引的速度很慢。
保存 NaN：不能使⽤indexOf()或 includes() 来查值 NaN，⽽ Set 可以保存此值。
删除重复项：Set对象只存储惟⼀的值，如果不想有重复项存在，相对于数组的⼀个显著优势，因为数组需要额外的代码来处理重复。
时间复杂度？
数组⽤来搜索元素的⽅法时间复杂度为0(N)。换句话说，运⾏时间的增长速度与数据⼤⼩的增长速度相同。
相⽐之下，Set⽤于搜索、删除和插⼊元素的⽅法的时间复杂度都只有O(1)，这意味着数据的⼤⼩实际上与这些⽅法的运⾏时间⽆关。
Set 究竟有多快？
虽然运⾏时间可能会有很⼤差异，具体取决于所使⽤的系统，所提供数据的⼤⼩以及其他变量，但我希望我的测试结果能够让你真实地了解Set的速度。 我将分享三个简单的测试和我得到的结果。
准备测试
在运⾏任何测试之前，创建⼀个数组和⼀个 Set，每个数组和 Set 都有100万个元素。为了简单起见，我从0开始，⼀直数到999999。let arr = [], set = new Set(), n = 1000000;
for (let i = 0; i < n; i++) {
arr.push(i);
set.add(i);
}
测试1：查元素
我们搜索数字123123let result;
console.time('Array');
result = arr.indexOf(123123) !== -1;
console.timeEnd('Array');
console.time('Set');
result = set.has(123123);
console.timeEnd('Set');Array: 0.173ms
Set: 0.023ms
Set 速度快了7.54倍
测试2：添加元素console.time('Array');
arr.push(n);
console.timeEnd('Array');
console.time('Set');
set.add(n);
console.timeEnd('Set');Array: 0.018ms
Set: 0.003ms
Set 速度快了6.73倍
测试3：删除元素
最后，删除⼀个元素，由于数组没有内置⽅法，⾸先先创建⼀个辅助函数：const deleteFromArr = (arr, item) => { let index = arr.indexOf(item);
return index !== -1 && arr.splice(index, 1);
};
这是测试的代码：console.time('Array');
deleteFromArr(arr, n);
console.timeEnd('Array');
console.time('Set');
set.delete(n);
console.timeEnd('Set');Array: 1.122ms
Set: 0.015ms
Set 速度快了74.13倍
总的来说，我们可以看到，使⽤Set 极⼤地改善运⾏时间。再来看看⼀些Set有⽤的实际例⼦。
案例1：从数组中删除重复的值
如果想快速地从数组中删除重复的值，可以将其转换为⼀个 Set。这是迄今为⽌过滤惟⼀值最简洁的⽅法:const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]
案例2：⾕歌⾯试问题
问题：
给定⼀个整数⽆序数组和变量 sum，如果存在数组中任意两项和使等于 sum 的值，则返回true。否则，返回false。例如，数组[3,5,1,4]和sum = 9，函数应该返回true，因为4 + 5 = 9。
解答
解决这个问题的⼀个很好的⽅法是遍历数组，创建 Set保存相对差值。
当我们遇到3时，我们可以把6加到Set中, 因为我们知道我们需要到9的和。然后，每当我们接触到数组中的新值时，我们可以检查它是否在 Set 中。当遇到5时，在 Set 加上4。最后，当我们最终遇到4时，可以在Set中到它，就返回true。const findSum = (arr, val) => {
let searchValues = new Set();
searchValues.add(val - arr[0]);
for (let i = 1, length = arr.length; i < length; i++) {
let searchVal = val - arr[i];
if (searchValues.has(arr[i])) {
return true;
} else {
javascript全局数组searchValues.add(searchVal);
}
};
return false;
};
简洁的版本：const findSum = (arr, sum) =>
arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
因为Set.prototype.has()的时间复杂度仅为O(1)，所以使⽤ Set 来代替数组，最终使整个解决⽅案的线性运⾏时为O(N)。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。