LeetCode - #26 从有序数组中移除重复数据
前言
我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。微博:@故胤道长[1])的 Swift 算法题题解整理为文字版以方便大家学习与阅读。
LeetCode 算法到目前我们已经更新了 25 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
难度水平:简单
1. 描述
给你一个 升序排列 的数组 nums
,请你 原地
删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度,所以必须将结果放在数组 nums 的第一部分。更规范地说,如果在删除重复项之后有 k
个元素,那么 nums
的前 k
个元素应该保存最终结果。
将最终结果插入 nums
的前 k
个位置后返回 k
。
不要使用额外的空间,你必须在 原地
修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过,那么您的题解将被 通过。
2. 示例
示例 1
输入:nums = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2 ,并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2
输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
约束条件:
0 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
-
nums
已按 升序 排列
3. 答案
class RemoveDuplicatesFromSortedArray {
func removeDuplicates(inout nums: [Int]) -> Int {
guard nums.count > 0 else {
return 0
}
var index = 0
for num in nums where num != nums[index] {
index += 1
nums[index] = num
}
return index + 1
}
}
- 主要思想:保留一个索引,将该索引处的元素与前面的元素进行比较。
- 时间复杂度: O(n)
- 空间复杂度: O(1)
该算法题解的仓库:LeetCode-Swift[2]
点击前往 LeetCode[3] 练习
特别感谢 Swift社区 编辑部的每一位编辑,感谢大家的辛苦付出,为 Swift社区 提供优质内容,为 Swift 语言的发展贡献自己的力量,排名不分先后:张安宇@微软[4]、戴铭@快手[5]、展菲@ESP[6]、倪瑶@Trip.com[7]、杜鑫瑶@新浪[8]、韦弦@Gwell[9]、张浩@讯飞[10]、张星宇@ByteDance[11]、郭英东@便利蜂[12]
参考资料
[1] @故胤道长: https://m.weibo.cn/u/1827884772
[2] LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift
[3] LeetCode: https://leetcode.com/problems/remove-duplicates-from-sorted-array/
[4] 张安宇: https://blog.****.net/mobanchengshuang
[5] 戴铭: https://ming1016.github.io
[6] 展菲: https://github.com/fanbaoying
[7] 倪瑶: https://github.com/niyaoyao
[8] 杜鑫瑶: https://weibo.com/u/3878455011
[9] 韦弦: https://www.jianshu.com/u/855d6ea2b3d1
[10] 张浩: https://github.com/zhanghao19920218
[11] 张星宇: https://github.com/bestswifter
[12] 郭英东: https://github.com/EmingK
推荐阅读
-
[ LeetCode ] 问题刷(Python) - 问题 26:从有序数组中删除重复数据
-
LeetCode - #26 从有序数组中移除重复数据
-
MAX_LEN) {
int pivot = partition(arr, left, right);
quicksort_optimized(arr, left, pivot - 1);
quicksort_optimized(arr, pivot + 1, right);
} else {
// 使用插入排序处理小数组
}
}
```
- 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如:
原序列: 1 4 6 7 6 6 7 6 8 6
- 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6
- 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6
- 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7
- 下次划分得到的子序列:1 4 和 7 8 7
通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。">
改进版快速排序:针对部分有序列的策略与优化技巧" - 随机选枢轴:当数据部分有序时,传统快速排序通过固定枢轴可能导致效率低下。为此,我们采用随机选取枢轴的方法,代码如下: ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换:针对小且部分有序的数组,快速排序不如插入排序高效。因此,当待排序序列长度小于等于10时,我们会切换至插入排序: ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (length > MAX_LEN) { int pivot = partition(arr, left, right); quicksort_optimized(arr, left, pivot - 1); quicksort_optimized(arr, pivot + 1, right); } else { // 使用插入排序处理小数组 } } ``` - 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如: 原序列: 1 4 6 7 6 6 7 6 8 6 - 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6 - 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6 - 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7 - 下次划分得到的子序列:1 4 和 7 8 7 通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。