【Leet Code】26. Remove Duplicates from Sorted Array

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://cloud.tencent.com/developer/article/1535447

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.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)

int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.

// using the length returned by your function, it prints the first len elements.

for (int i = 0; i < len; i++) {

 print(nums[i]);

}

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

辣鸡代码

int removeDuplicates(int* nums, int numsSize){
    int p1=0,p2=0;
    for(int p2=1;p2<numsSize;p2++){
        if(nums[p2]!=nums[p1]) nums[++p1]=nums[p2];
    }
    return numsSize>0 ? p1+1:0;
}

特别简单一道题，给我整的却听够呛

刚开始做是挺多问题的

多练练可能就好了呢~？

榜首人的做法：

int removeDuplicates(int* nums, int numsSize){

    int val = nums[0];
    int index = 1;
    int match_count = 0;
    
    if(numsSize == 0) {
        return 0;
    }
    
    for (int i = 1; i < numsSize; i++) {
        if (val != nums[i]) {
            nums[index] = nums[i];
            index++;
            val = nums[i];
        } else {
            match_count++;
        }
    }
    return numsSize - match_count;
}

方法：双指针法算法

数组完成排序后，我们可以放置两个指针 ii 和 jj，其中 ii 是慢指针，而 jj 是快指针。只要 numsi = numsjnumsi=numsj，我们就增加 jj 以跳过重复项。

当我们遇到 numsj \neq numsinumsj



​

=numsi 时，跳过重复项的运行已经结束，因此我们必须把它（numsjnumsj）的值复制到 numsi + 1numsi+1。然后递增 ii，接着我们将再次重复相同的过程，直到 jj 到达数组的末尾为止。

Java

public int removeDuplicates(int[] nums) {

 if (nums.length == 0) return 0;

 int i = 0;

 for (int j = 1; j < nums.length; j++) {

     if (nums[j] != nums[i]) {

         i++;

         nums[i] = nums[j];

     }

 }

 return i + 1;

}

复杂度分析

时间复杂度：O(n)O(n)，假设数组的长度是 nn，那么 ii 和 jj 分别最多遍历 nn 步。

空间复杂度：O(1)O(1)。

作者：LeetCode

链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-xiang-by-/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。