LintCode (100) Remove Duplicate From Sorted Array

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.

Have you met this question in a real interview? 

Yes

Example

Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

两根指针， 一个慢，一个快，慢的负责往里写，快的负责找unique value...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { // write your code here if (nums.empty()) return 0; int beg=0; int end=0; while(end<nums.size()){ while(end<nums.size()-1 && nums[end]==nums[end+1]) end++; nums[beg++]=nums[end++]; } return beg; } };

看了下自己两个月以前写的，反正思路都一样。。。不过貌似这个可读性高些。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

class Solution { public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { // write your code here int n=nums.size(); if (n<=1) return n; int beg=0; int end=beg+1; while(end<n){ if (nums[beg]==nums[end]){ end++; } else{ nums[++beg]=nums[end++]; } } return beg+1; } };