欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何去除有序数组的重复元素

程序员文章站 2022-07-14 07:59:05
...

参考公众号:labuladong

对于数组来说,在尾部插⼊、删除元素是⽐较⾼效的,时间复杂度是 O(1),但是如果在中间或者开头插⼊、删除元素,就会涉及数据的搬移,时间复杂度为 O(N),效率较低。
所以对于⼀般处理数组的算法问题,我们要尽可能只对数组尾部的元素进⾏操作,以避免额外的时间复杂度
如何去除有序数组的重复元素
显然,由于数组已经排序,所以重复的元素⼀定连在⼀起,找出它们并不难,但如果毎找到⼀个重复元素就⽴即删除它,就是在数组中间进⾏删除操作,整个时间复杂度是会达到 O(N^2)。⽽且题⽬要求我们原地修改,也就是说不能⽤辅助数组,空间复杂度得是 O(1)

对于数组相关的算法问题,有⼀个通⽤的技巧:要尽量避免在中间删除元素,那我就想先办法把这个元素换到最后去。这样的话,最终待删除的元素都拖在数组尾部,⼀个⼀个 pop 掉就⾏了,每次操作的时间复杂度也就降低到 O(1) 了。
按照这个思路呢,⼜可以衍⽣出解决类似需求的通⽤⽅式:双指针技巧。具体⼀点说,应该是快慢指针。

我们让慢指针 slow ⾛左后⾯,快指针 fast ⾛在前⾯探路,找到⼀个不重复的元素就告诉 slow 并让 slow 前进⼀步。这样当 fast 指针遍历完整个数组 nums 后, nums[0…slow] 就是不重复元素,之后的所有元素都是重复元素。
因为数组有序,slow指向不重复区域的最后一个

int removeDuplicates(int[] nums){
	int n = nums.length;
	if(n==0 || n==1) return 0;
	int slow = 0, fast = 1;
	while(fast < n){
		if(nums[fast] != nums[slow]){
			slow++;
			//维护nums[0...slow]无重复
			nums[slow] = nums[fast];
		}
		fast++;
	}
	//长度为索引+1
	return slow + 1;
}

如何去除有序数组的重复元素
如果给你⼀个有序链表,如何去重呢?其实和数组是⼀模⼀样的,唯⼀的区别是把数组赋值操作变成操作指针⽽已:
slow指针把不同的节点串起来

ListNode deleteDuplicates(ListNode head) {
	if (head == null) return null;
	ListNode slow = head, fast = head.next;
	while (fast != null) {
		if (fast.val != slow.val) {
			// nums[slow] = nums[fast];
			slow.next = fast;
			// slow++;
			slow = slow.next;
		}
		// fast++
		fast = fast.next;
	}
	// 断开与后⾯重复元素的连接
	slow.next = null;
	return head;
}

如何去除有序数组的重复元素

相关标签: 高频面试

上一篇: ActiveMQ--topic

下一篇: kafka优点