Remove Duplicates from Sorted Array
LeetCode笔记 阅读(463)
编号 : 26 难度 : <font color="green">Easy</font> # 题目 : >Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. > >Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory. > >**Example 1**: > >>Given nums = [1,1,2], >> >>Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. >> >>It doesn't matter what you leave beyond the returned length. > >**Example 2**: > >>Given nums = [0,0,1,1,1,2,2,3,3,4], >> >>Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively. >> >>It doesn't matter what values are set beyond the returned length. > >**Clarification**: > >Confused why the returned value is an integer but your answer is an array? > >Note that the input array is passed in by **reference**, which means modification to the input array will be known to the caller as well. > >Internally you can think of this: > >``` >// nums is passed in by reference. (i.e., without making a copy) >int len = removeDuplicates(nums); > >// any modification to nums in your function would be known by the caller. >// using the length returned by your function, it prints the first len elements. >for (int i = 0; i < len; i++) { > print(nums[i]); >} >``` > # 解 : ```Cpp class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() == 0) { return 0; } int current = nums[0]; int count = nums.size(); for(int i = 1; i < count; ) { if(nums[i] == current) { /* 发现重复的数据,把后面的数据往前移动,覆盖掉这个值 */ for(int j = i + 1; j < count; j++) { nums[j - 1] = nums[j]; } count--; } else { current = nums[i]; i++; } } return count; } }; ``` # 分析 : 这道题要求删除有序数组中重复的数值,只要将不重复的值放在数组开头并返回正确的长度即可,尾部多余的部分可以不用处理。 上述解法中从头开始搜索数组,发现重复的值,就将数组后面的部分向前移动,覆盖掉它,整体的时间复杂度是`O(n^2)`,非常慢。 ## 更快的办法 没有必要在发现重复的值的时候整体移动,只需要找到**不重复**的值并提取到数组开头即可,这样做的时间复杂度是`O(n)` : ```Cpp class Solution { public: int removeDuplicates(vector<int>& nums) { if(nums.size() == 0) { return 0; } int index = 1; // 指示要插入的位置 for(int i = 1; i < nums.size(); i++) { if(nums[i] != nums[index-1]) { nums[index] = nums[i]; index += 1; } } return index; } }; ``` 运行结果 : | 方案 | Runtime | Memory | | :-: | :-: | :-: | | O(n^2) | 424 ms | 10 MB | | O(n) | 16 ms | 9.9 MB |
Cialis Vantaggi Rafabolotomb <a href=https://bansocialism.com/>purchase cialis online cheap</a> reurgy Viagra 35 Anos