您现在的位置是:首页 >技术交流 >精妙绝伦的算法之舞:解密力扣“删除有序数组中的重复项”网站首页技术交流
精妙绝伦的算法之舞:解密力扣“删除有序数组中的重复项”
本篇博客会讲解力扣“26. 删除有序数组中的重复项”这道题,这是题目链接。
老规矩,先来审题:
题目有对判题标准的详细解释:
接下来是2个示例:
还有提示:
其实这道题考察的是“去重算法”,即去除一个非递减序列的重复项。举个很简单的例子,把[0 0 1 2 2 2 3 4 4 5]变成类似[0 1 2 3 4 5]这样就行了。大家可以先思考一下,再来听我讲解。
这种考察数组的题目,大部分都是采用“双指针”或者“双下标”的方法。这里我用“双下标”的思路来讲解。
首先需要有2个下标。第一反应:2个下标都是0可不可以?我们顺着这个思路想一想:这道题是“去重”,所以一定要判断2个下标对应的元素是不是“相同”,因为“相同”意味着“重复”。如果2个下标一开始都是0,那就没有比较的意义了,因为这是同一个元素,一定是相等的。
所以,最好是2个下标一前一后。假设一个下标是0,另一个下标是1,这样这2个下标对应的元素就有了比较的意义。
下面再提一下大部分“双下标”思路的共性:一般都有一个是dst,表示目标;另一个是src,表示源头。目标一般标识“可以存储有效数据的位置”,源头一般是用来遍历数组的。
所以,我们的思路是:dst负责记录最后一个有效数据的位置,因为第一个数据一定是有效的,所以一开始初始化成0很合理。src则负责遍历数组,如果找到“有效”的数据,就存储在dst的位置后面。什么是“有效”的数据呢?和前面的数据不重复就是有效的数据了。
先搭个架子:
int removeDuplicates(int* nums, int numsSize){
int dst = 0; // 标识最后一个有效数据
int src = 1; // 遍历数组
while (src < numsSize)
{
if (nums[src] == nums[dst])
{
// src无效
}
else
{
// src有效
}
}
}
那src“有效”和“无效”时分别应该如何处理呢?
如果数据无效,直接跳过这个数据即可;如果数据有效,那么就把这个数据存储在当前dst的数据后面,因为dst标识最后一个有效数据。
最后return什么呢?因为dst是最后一个有效数据的下标,+1就是有效数据的个数。
int removeDuplicates(int* nums, int numsSize){
int dst = 0; // 标识最后一个有效数据
int src = 1; // 遍历数组
while (src < numsSize)
{
if (nums[src] == nums[dst])
{
// src无效
++src;
}
else
{
// src有效
nums[++dst] = nums[src++];
}
}
return dst + 1;
}
这样就通过了,非常完美。
总结
- 数组问题善用“双下标”法。
- 要明白“双下标”中每个下标的意义,本题中,一个标识最后一个有效数据,另一个用来遍历。
感谢大家的阅读!