小工具知识网

当前位置: 首页 > 行业知识 > 代码训练LeetCode(7)删除有序数组中的重复项

行业知识

代码训练LeetCode(7)删除有序数组中的重复项

2026-11-18 00:33:00 来源:互联网转载

代码训练(7)LeetCode之删除有序数组中的重复项

Author: Once Day Date: 2024年3月10日

漫漫长路,才刚刚开始…

全系列文章可参考专栏: 十年代码训练_Once-Day的博客-CSDN博客

参考文章:

  • 26. 删除有序数组中的重复项 - 力扣(LeetCode)
  • 力扣 (LeetCode) 全球极客挚爱的技术成长平台

    文章目录

        • 代码训练(7)LeetCode之删除有序数组中的重复项
          • 1. 原题
          • 2. 分析
          • 3. 代码实现
            • 3.1 基础实现
            • 3.2 过度优化版本代码
            • 4. 总结
              1. 原题

              给你一个 非严格递增排列 的数组 nums ,请你原地删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

              考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

              • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
              • 返回 k 。

                例如,对于nums = [1, 2, 2, 3],其输出长度为3,输出数据为nums = [1, 2, 3, x]即可。

                2. 分析

                有一个数组 nums,它是非严格递增的,也就是说,数组中的元素可能会有重复,并且它们是按照顺序排列的。你的任务是要在不改变元素相对顺序的情况下,仅保留每个元素的一个副本,并删除所有的重复元素。你需要在不使用额外数组的条件下完成这个操作,这就意味着你需要在原地修改输入的数组 nums。

                解题思路:

                1. 保持两个指针,i 作为慢指针,j 作为快指针。
                2. 遍历数组,快指针 j 用于寻找下一个与慢指针 i 指向的数字不同的数字。
                3. 当快指针 j 找到一个新的不同数字时,将慢指针 i 向前移动一位,然后将 j 指向的数字复制到 i 的位置。
                4. 重复步骤2和3,直到快指针 j 遍历完整个数组。

                分析步骤:

                • 初始化两个指针 i 和 j,其中 i = 0,j = 1。
                • 当j小于数组nums的长度时,执行以下操作:
                  • 如果 nums[j] 与 nums[i] 相同,j++,跳过重复的元素。
                  • 如果 nums[j] 与 nums[i] 不同,i++,并将 nums[j] 的值赋给 nums[i]。
                  • 继续执行上述步骤直到 j 遍历完数组。
                  • 最终,i+1 就是数组中不重复元素的个数。

                    举例分析:

                    如果输入的数组 nums 为 [1, 1, 2],初始时 i=0,j=1。

                    • 因为 nums[j] 等于 nums[i],所以 j++,现在 j=2。
                    • 现在 nums[j] 不等于 nums[i],所以 i++,将 nums[j] 的值赋给 nums[i],现在 nums 变为 [1, 2, 2]。
                    • j 继续递增,因为已经到数组末尾,停止循环。
                    • 最终 i+1 等于 2,表示数组 nums 中有两个不重复的元素。

                      性能优化关键点:

                      • 尽量减少不必要的操作,例如在快指针找到新元素时才移动慢指针。
                      • 避免使用额外的内存空间,直接在原数组上操作。
                        3. 代码实现
                        3.1 基础实现
                        int removeDuplicates(int* nums, int numsSize) {    if (numsSize == 0) return 0;    int i = 0;    for (int j = 1; j  

                        这段代码含义如下:

                        • removeDuplicates 函数接受一个整数数组 nums和它的大小 numsSize,然后返回一个整数表示唯一元素的数量。
                        • 在 main 函数中,我们定义了一个示例数组并调用 removeDuplicates 函数。
                        • 然后打印出修改后的数组和唯一元素的数量。

                          运行测试结果如下(仅供参考):

                          这段代码性能不算非常高,因为存在nums[i]这种随机访问,并且判断nums[j] != nums[i]在大部分情况也有些多余。

                          3.2 过度优化版本代码

                          注意,本部分代码仅供各位C语言爱好者一乐,真实项目别写这种风格代码,上面3.1简单版本的代码更合适。

                          struct temp{    int last;    int curr;};int removeDuplicates(int* nums, int numsSize) {    int *deal_nums, *resv_nums, *max_nums;#define unlikely(x) __builtin_expect(!!(x), 0)#define likely(x) __builtin_expect(!!(x), 1)    if (unlikely(numsSize         return numsSize;    }    max_nums  = &nums[numsSize] - 1;    deal_nums = nums;    resv_nums = &nums[1];    while(likely(deal_nums last) {            if (deal_nums != resv_nums) {                *resv_nums = temp->curr;                goto another;            }            resv_nums++;        }     }    while(likely(deal_nums curr ^ temp->last) {            *resv_nums = temp->curr;another:            resv_nums++;        }     }    return resv_nums - nums;}

                          代码中使用了一个结构体 temp,包含两个整型成员 last 和 curr,用于同时存储相邻的两个元素。

                          主要的优化点如下:

                          1. 使用 unlikely 和 likely 宏来优化分支预测,提高代码执行效率。
                          2. 使用指针操作来遍历数组,避免了数组下标的计算,提高了性能。
                          3. 使用异或运算 ^ 来比较相邻元素是否相等,避免了条件分支的使用,提高了性能。
                          4. 使用 goto 语句来优化代码流程,减少了重复的代码。

                          缺点也很明显:

                          • 代码可读性较差,使用了一些技巧性的优化,如位运算和 goto 语句,可能会影响代码的可维护性。
                          • 虽然使用了一些优化手段,但整体的时间复杂度仍然是 O(n),与普通的去重算法相比,优化的效果可能并不明显。

                            这段代码在一定程度上提高了去重操作的性能,但也牺牲了一定的可读性和可维护性。

                            实际运行结果如下(仅供参考):

                            4. 总结

                            这个题目考查了对数组操作的基本能力,特别是双指针技巧,这是一个常用于解决类似问题的方法。为了提高编程能力,应当熟练掌握数组相关的操作,包括但不限于遍历、插入、删除等。

                            同时,熟悉双指针技巧在其他问题中的应用也非常重要,即如何在不使用额外空间的情况下修改输入数据。

                            Once Day

                            也信美人终作土,不堪幽梦太匆匆......

                            如果这篇文章为您带来了帮助或启发,不妨点个赞和关注,再加上一个小小的收藏⭐!

                            (。◕‿◕。)感谢您的阅读与支持~~~

上一篇:服务器项目备份查询在哪里?

下一篇:短音下载指南,轻松获取,极速安装,一键开启音乐之旅!