leetcode解题: Remove Duplicates from Sorted Array (26)

发表于 | 分类于

Given a sorted array, 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 in place with constant memory.

For example,
Given input array 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 new length.

解法1：Two pointers

思路和Remove elements一样，不一样的是two pointers指向的位置不同。这题由于是sorted，那么可以用一个指针指向插入的位置，只有碰到和前面不一样的数值的时候才更新他的值。
最后由于是返回count，所以要注意是把第一个指针的数值+1.
举例：1 2 3 3 4
当1，2，3 都不一样的时候，slow的指针往前进。当碰到第二个3的时候，slow不变，当碰到4时，把4赋值给第二个3，也就是当前slow的位置。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int slow = 0;
        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] != nums[i -1]) {
                nums[++slow] = nums[i];
            }
        }
        return slow + 1;
    }
};

Java

1