力扣26题（双指针法）

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

26.给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

1. 暴力解法就用3个for循环嵌套，第一层用于改变扫描值，第二层用于扫描整个数组找到重复元素，第三层用于移动元素。时间复杂度过高，只是尝试看能否写出来，没有什么实际意义。

int removeDuplicates(int* nums, int numsSize){
    int temp = 0;
    for (int i = 0; i < numsSize; i ++) {
        temp = nums[i];
        for (int j = i + 1; j < numsSize; j ++) {
            if (nums[j] == temp) {
                for (int k = j; k < numsSize - 1; k ++) {
                    nums[k] = nums[k + 1];
                }
                numsSize --;
            }
            if (nums[j] == temp)
                j --;
        }
    }
    return numsSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 第二种解法是双指针法，利用一个快指针和慢指针，用一个for循环来替换掉暴力解法内两层for循环。时间复杂度减少很多。

int removeDuplicates(int* nums, int numsSize){
    int temp = 0;
    for (int i = 0; i < numsSize; i ++) {
        temp = nums[i];
        int slow = i + 1;
        for (int fast = i + 1; fast < numsSize; fast ++) {
            if (nums[fast] != temp) {
                nums[slow ++] = nums[fast];
            }
        }
        numsSize = slow;
    }
    return numsSize;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14