趣味算法题

越刷越上头的趣味算法题
帅旋
关注
充电
IT宅站长,技术博主,架构师,全网id:arthinking。

快慢指针经典题目:删除有序数组中的重复项

发布于 2024-03-13 | 更新于 2024-08-21

题目:26. 删除有序数组中的重复项[1]

如果您已经有思路了,或者是N刷了,可以先自己写一遍。

题目分析

这也是一个比较常见的问题,设计目标是就地(不使用额外的数组空间)删除排序数组中的重复元素,使得每个元素只出现一次,并返回修改后数组的新长度。

我们可以使用快慢针技术。这个技术的核心思想是使用两个指针在一次遍历中完成任务:一个慢指针 i,一个快指针 j

解题思路

快指针用于探索数组前面,而慢指针标记了无重复数组的当前结束位置。

当我们遇到一个新的元素(即与慢指针指向的元素不同的元素),我们就将它复制到慢指针的下一个位置,然后两个指针都前进一步。

如果快指针指向的元素与慢指针指向的元素相同,我们只将快指针前进一步。

这样,当快指针遍历完整个数组时,从数组的开始到慢指针的位置就是无重复元素的数组,且我们没有使用额外的空间。

Java解法

下面是使用Java语言的解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[j] != nums[i]) {
i++;
nums[i] = nums[j];
}
}
return i + 1; // 返回新的数组长度
}
}

这种方法的优点是空间复杂度低(O(1)),因为它不需要额外的存储空间来存储结果。

这个技巧在处理有序数组或链表中的问题时非常有用,能够有效地减少不必要的数据移动或复制,从而提高算法的效率。

References


  1. 26. 删除有序数组中的重复项. Retrieved from https://leetcode.cn/problems/remove-duplicates-from-sorted-array/ ↩︎

本文作者: 帅旋

本文链接: https://www.itzhai.com/columns/algorithm/remove-duplicates-from-sorted-array.html

版权声明: 版权归作者所有,未经许可不得转载,侵权必究!联系作者请加公众号。

×
IT宅

关注公众号及时获取网站内容更新。

请帅旋喝一杯咖啡

咖啡=电量,给帅旋充杯咖啡,他会满电写代码!

IT宅

关注公众号及时获取网站内容更新。