🥳每日一练-删除数组中重复的元素-JS简易版

站长

2023年11月22日 15:04 · 阅读数 26

这篇文章分享一个新的数据结构--散列表，并用散列表解决一个算法问题：删除数组中重复的数字

对于这个问题，如果数组是有序的，那算法的复杂度可以降到 O(n); 如果是无序的，一不小心就会变成 O(nlogn)的复杂度

在 JS 中，无论数组是否有序，都可以使用语言本身支持的数据结构 API，Set 或者 Map 来解决，像下面这样：

const deleteDupBySet = (array)=>{
  return [...new Set(array)];
}

如果不借助这些 API，你会怎么解决这个问题呢？

有序的数组

在遍历数组的过程中，如果发现相同的元素，就用后面的元素覆盖之前的重复元素。即如果发现了一个，后面的元素就往前移动一个；如果发现了两个，后面的元素都往前移动两格；

/**
 *
 * @param {number[]} array
 */
const deleteDuplicSorted = (array) => {
	let k = 0;
	for (let i = 1; i < array.length; ) {
		if (array[i - k - 1] == array[i]) {
			k++;
		} else {
			array[i - k] = array[i];
			i++;
		}
	}
	array.length = array.length - k;
	return array;
};

上述代码定义了一函数，接收数组作为参数。这个函数会将 array 中的重复元素都删除，最后返回 array；

函数中用 K 记录重复元素的个数。当遇到相同的元素是，k++，然后继续比较下一个元素；当遇到不同的元素的时候，就可以讲这个元素往前挪了，挪动的幅度就是 k。遍历结束之后，需要将 array 的长度减 k。

测试代码

const data = [1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9, 9, 9];
console.log(deleteDuplicSorted(data));
// [
//   1, 2, 3, 4, 5,
//   6, 7, 8, 9
// ]

测试成功

无序的数组

如果数组是无序的，用上面的方法就行不通了。这其中的关键是，确认元素是否重复。需要拿到一个元素都要遍历整个数组才能确认它是否重复吗？

如果不这么做，可不可以先给无序的数组排个序呢？然后再遍历删除重复的元素。这样做可以是可以，但会增加复杂度，排序最短的复杂度是 O(nlogn), 然后还需要遍历数组，整个复杂度就是 O(n + nlogn)

有没有更高效的办法呢，有的。我们可以借助散列表来降低确认元素的复杂度。

class HashList {
	constructor(number) {
		this.list = Array(number).fill(null);
		this.len = number;
	}

	isHas(value) {
		const hashValue = value % this.len;
		let linkList = this.list[hashValue];
		while (linkList) {
			if (linkList.value == value) return true;
			linkList = linkList.next;
		}

		this._insert(hashValue, value);
		return false;
	}
	_insert(index, value) {
		const linkList = this.list[index];
		const temp = { value, next: null };
		if (linkList == null) {
			this.list[index] = temp;
		} else {
			// 头插法
			temp.next = linkList.next;
			linkList.next = temp;
		}
	}
}

这里定义了一个散列表的数据结构--HashList

这里使用散列表的定位方式除留余数法，即将元素对一个特定的树取余，来决定释放在散列表的哪个位置；冲突崇礼的方式是拉链法，即如果元素定位到了散列表相同的位置，就会用链表的方法串在一起，不影响散列表的其他位置。像下面这样： 🥳每日一练-删除数组中重复的元素-JS简易版

此图来自 B站王道数据结构视频课

HashList 还有两个函数，isHas 和 _insert，isHas 是判断元素是否存在于散列表中，可以借助这个方法来判断元素是否重复。如果监测到已经存在于散列表中，就说明元素重复了。如果元素不在散列表中，就是自动调用_insert 方法，将元素插入到散列表。_insert 是供内部调用的一个方法，直接插入到散列表的指定位置

/**
 *
 * @param {number[]} array
 */
const deleteDupByHash = (array) => {
	const hashList = new HashList(array.length);
	let k = 0;
	for (let i = 0; i < array.length; i++) {
		if (hashList.isHas(array[i])) {
			k++;
		} else {
			array[i - k] = array[i];
		}
	}
	array.length = array.length - k;
	return array;
};

这里定义了一个函数 deleteDupByHash，其中借助了 HashList 实现了删除无序数组中的重复元素。遍历数组的逻辑和之前一样，即如果发现了一个重复元素，后面的元素就往前移动一个；如果发现了两个重复元素，后面的元素都往前移动两格；

测试代码：

const data = [1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9, 9, 9];
console.log(deleteDupByHash(data));
// [
//   1, 2, 3, 4, 5,
//   6, 7, 8, 9
// ]

测试成功

完整代码

/**
 *
 * @param {number[]} array
 */
const deleteDuplicSorted = (array) => {
	let k = 0;
	for (let i = 1; i < array.length; ) {
		if (array[i - k - 1] == array[i]) {
			k++;
		} else {
			array[i - k] = array[i];
			i++;
		}
	}
	array.length = array.length - k;
	return array;
};
class HashList {
	constructor(number) {
		this.list = Array(number).fill(null);
		this.len = number;
	}

	isHas(value) {
		const hashValue = value % this.len;
		let linkList = this.list[hashValue];
		while (linkList) {
			if (linkList.value == value) return true;
			linkList = linkList.next;
		}

		this._insert(hashValue, value);
		return false;
	}
	_insert(index, value) {
		const linkList = this.list[index];
		const temp = { value, next: null };
		if (linkList == null) {
			this.list[index] = temp;
		} else {
			// 头插法
			temp.next = linkList.next;
			linkList.next = temp;
		}
	}
}
/**
 *
 * @param {number[]} array
 */
const deleteDupByHash = (array) => {
	const hashList = new HashList(array.length);
	let k = 0;
	for (let i = 0; i < array.length; i++) {
		if (hashList.isHas(array[i])) {
			k++;
		} else {
			array[i - k] = array[i];
		}
	}
	array.length = array.length - k;
	return array;
};

//测试
const data = [1, 2, 2, 3, 3, 4, 4, 4, 4, 5, 6, 7, 8, 9, 9, 9];

console.log(deleteDuplicSorted([..data]));

console.log(deleteDupByHash([...data]));

总结

这篇文章分享了如何删除数组中的重复元素，并且提到了有序数组和无序数组的处理方法，都是复杂度最低的方案。代码清晰，例子丰富，讲解详细，是个不可多得的好文章

你觉得这篇文章怎么样？我每天都会分享一篇算法小练习，喜欢就点赞+关注吧