題目

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.

解題之法

class Solution {
public:
    int removeDuplicates(vector<int>& A) {
        int n = A.size();
        if (n <= 1) return n;
        int pre = 0, cur = 0;
        while (cur < n) {
            if (A[cur] == A[pre]) ++cur;
            else A[++pre] = A[cur++];
        }
        return pre + 1;
    }
};

分析

這道題要我們從有序數(shù)組中去除重復(fù)項(xiàng)，我們使用快慢指針來記錄遍歷的坐標(biāo)，最開始時(shí)兩個(gè)指針都指向第一個(gè)數(shù)字，如果兩個(gè)指針指的數(shù)字相同，則快指針向前走一步，如果不同，則兩個(gè)指針都向前走一步，這樣當(dāng)快指針走完整個(gè)數(shù)組后，慢指針當(dāng)前的坐標(biāo)加1就是數(shù)組中不同數(shù)組的個(gè)數(shù)，