您现在的位置是:首页 >技术交流 >精妙绝伦的算法之舞:解密力扣“删除有序数组中的重复项”网站首页技术交流

精妙绝伦的算法之舞:解密力扣“删除有序数组中的重复项”

努力学习游泳的鱼 2024-06-03 10:56:09
简介精妙绝伦的算法之舞:解密力扣“删除有序数组中的重复项”

在这里插入图片描述

本篇博客会讲解力扣“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;
}

在这里插入图片描述
这样就通过了,非常完美。

总结

  1. 数组问题善用“双下标”法。
  2. 要明白“双下标”中每个下标的意义,本题中,一个标识最后一个有效数据,另一个用来遍历。

感谢大家的阅读!

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。