[LeetCode]26. Remove Duplicates from Sorted Array

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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.

Solution

Analysis

删除有序数组中的重复数字, 但是不完全删除完,剩一个. 要求空间复杂度为O(1).

因为是有序数组,所以重复数字都是连续出现的. 根据这个现象, 可以利用快排中的merge函数的思想, 使用一个指针指向最终结果的下标, 一个指针用来遍历原数组, 如果不是第一次出现, 则存到最终结果的有序数组里.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        int idx = 0;// 最终结果数组的下标: 右边界[包含]
        
        for (int i=1; i< nums.size(); i++)
            if (nums[i] != nums[idx])//不等
                nums[++idx] = nums[i];// 放进数组中
        return idx+1;// 返回个数
        
        //return distance(nums.begin(), unique(nums.begin(), nums.end()));
    }
};
您的支持就是我更新的最大动力!谢谢!