1. 题目描述

problem link

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.

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.

2. 解题

使用两个指针i和j，i作为慢指针j作为快指针。首先把i初始化为0，j 初始化为1。arr[i] == arr[j] 的时候让j++以跳过重复元素，而当j找到了一个不等于arr[i]的元素时，将这个元素赋值到下标i的下一个位置。

下面用图来表示一下这个方法的原理。

首先i指向第一个元素，j指向第二个元素，如果nums[i] == nums[j]，就让j++直到找到一个不等于arr[i]的元素。

此时j找到了一个不等于arr[i]的元素，根据题意，需要把这个元素赋值到i的下一个位置，所以先让 i++，再进行赋值，最后再让j++。

看到此时j走出了数组区域，所以程序结束，最终数组中的有效元素个数为i+1。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int removeDuplicates(int* nums, int numsSize) {
    if (numsSize == 0) {
        return numsSize;
    }

    int i = 0, j = 1;
    while (j < numsSize) {
        if (nums[i] != nums[j]) {
            i++;
            nums[i] = nums[j];
        }
        j++;
    }

    return i + 1;
}

int main() {
    int arr[] = { 1, 1, 2 };
    int res = removeDuplicates(arr, sizeof(arr) / sizeof(arr[0]));
    printf("res = %d\n", res);
    printf("\n");

    system("pause");
    return 0;
}