行业知识
代码训练LeetCode(7)删除有序数组中的重复项
代码训练(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。
解题思路:
- 保持两个指针,i 作为慢指针,j 作为快指针。
- 遍历数组,快指针 j 用于寻找下一个与慢指针 i 指向的数字不同的数字。
- 当快指针 j 找到一个新的不同数字时,将慢指针 i 向前移动一位,然后将 j 指向的数字复制到 i 的位置。
- 重复步骤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,用于同时存储相邻的两个元素。
主要的优化点如下:
- 使用 unlikely 和 likely 宏来优化分支预测,提高代码执行效率。
- 使用指针操作来遍历数组,避免了数组下标的计算,提高了性能。
- 使用异或运算 ^ 来比较相邻元素是否相等,避免了条件分支的使用,提高了性能。
- 使用 goto 语句来优化代码流程,减少了重复的代码。
缺点也很明显:
- 代码可读性较差,使用了一些技巧性的优化,如位运算和 goto 语句,可能会影响代码的可维护性。
- 虽然使用了一些优化手段,但整体的时间复杂度仍然是 O(n),与普通的去重算法相比,优化的效果可能并不明显。
这段代码在一定程度上提高了去重操作的性能,但也牺牲了一定的可读性和可维护性。
实际运行结果如下(仅供参考):
4. 总结
这个题目考查了对数组操作的基本能力,特别是双指针技巧,这是一个常用于解决类似问题的方法。为了提高编程能力,应当熟练掌握数组相关的操作,包括但不限于遍历、插入、删除等。
同时,熟悉双指针技巧在其他问题中的应用也非常重要,即如何在不使用额外空间的情况下修改输入数据。
Once Day
也信美人终作土,不堪幽梦太匆匆......
如果这篇文章为您带来了帮助或启发,不妨点个赞和关注,再加上一个小小的收藏⭐!
(。◕‿◕。)感谢您的阅读与支持~~~