Remove Duplicates from Sorted Array

Posted on Edited on In Views:

26.Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

return k after placing the final result in the first k slots of nums.

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:

1
2
3
4
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

1
2
3
4
Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

个人解答：

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
int removeDuplicates(vector<int>& nums) {
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    return nums.size();
}

双指针：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int removeDuplicates(vector<int>& nums) {
    int nums_size = nums.size();
    if (nums_size == 1)return 1;
    int left = 0;
    int right = 1;
    while (right < nums_size) {
        if (nums[right] != nums[left]) {
            if (right - left > 1) {//right和left相邻不用复制
                nums[left + 1] = nums[right];
            }
            left++;
        }
        right++;
    }
    return left+1;
}
1
2
3
4
5
6
7
8
9
10
int removeDuplicates(vector<int> arr) {
    if (arr.empty()) return 0;
    int index = 0;
    for (int val : arr) {
        if (val != arr[index]) {
            arr[++index] = val;
        }
    }
    return index + 1;
}