讨论/《初级算法》 - 删除排序数组中的重复项/
《初级算法》 - 删除排序数组中的重复项
共 328 个回复

因为数组是排序的,只要是相同的肯定是挨着的,我们只需要遍历所有数组,然后前后两两比较,如果有相同的就把后面的给删除。

1,双指针解决

使用两个指针,右指针始终往右移动

  • 如果右指针指向的值等于左指针指向的值,左指针不动。
  • 如果右指针指向的值不等于左指针指向的值,那么左指针往右移一步,然后再把右指针指向的值赋给左指针

具体看下视频

来看下代码

    //双指针解决
    public int removeDuplicates(int[] A) {
        //边界条件判断
        if (A == null || A.length == 0)
            return 0;
        int left = 0;
        for (int right = 1; right < A.length; right++)
            //如果左指针和右指针指向的值一样,说明有重复的,
            //这个时候,左指针不动,右指针继续往右移。如果他俩
            //指向的值不一样就把右指针指向的值往前挪
            if (A[left] != A[right])
                A[++left] = A[right];
        return ++left;
    }


或者还可以换一种解法,其实原理都是一样的。

    public int removeDuplicates(int[] A) {
        int count = 0;//重复的数字个数
        for (int right = 1; right < A.length; right++) {
            if (A[right] == A[right - 1]) {
                //如果有重复的,count要加1
                count++;
            } else {
                //如果没有重复,后面的就往前挪
                A[right - count] = A[right];
            }
        }
        //数组的长度减去重复的个数
        return A.length - count;
    }


我把部分算法题整理成了PDF文档,截止目前总共有1000多页,大家可以下载阅读
链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

如果觉得有用就给个赞吧,还可以关注我的LeetCode主页查看更多的详细题解

239
int removeDuplicates(int* nums, int numsSize){
    int j = numsSize;
    if(j > 1){
        j = 1;
        for(int i = 1; i < numsSize; i ++){
            if(nums[i] == nums[i - 1]){
                continue;
            } else{
                nums[j] = nums[i];
                j++;
            }
        }
    }
    return j;
}
63

C++ 标准库函数

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
        return nums.size();
    }
};
47

python逆序删除

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in range(len(nums) - 1, 0, -1):
            if nums[i] == nums[i - 1]:
                del nums[i]
        return len(nums)
43
class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;

        for (int j = 1; j < nums.length; j++) {
            if (nums[i] != nums[j]) {
                i++;
                nums[i] = nums[j];
            }
        }

        return i + 1;
    }
}
32

这简直是作弊

18

常规操作,先去除异常场景。把数组是null和数组为空的情况排除。
由于题目要求只能在原数组上删除,且该数组是个排好序的数组。那么我们可以定义一个游标 index,来记录需要替换为后面数据的位置。由于第一个元素肯定是要保留在数组中的,因此起始,我们将游标指向数组的第二个元素(此位置为可能替换元素的位置),数组下标指向第二个元素。判断游标指向位置的前一个元素的值和当前获取的数组下标值是否相同。若相同,则游标位置不变,数组下标后移。若不同,代表需要把新元素替换到游标指向的位置。则替换元素,并且游标指向下一个位置,计数项加一。
按此操作循环整个数组可得到最终结果。

public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int count = 1;
        int index = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[index - 1]) {
                continue;
            }
            nums[index] = nums[i];
            index++;
            count++;
        }
        return count;
    }
15

[1, 2, 3, 4]
当 i = 1 的时候,你删除了元素 2 ,然后元素 3 的下标就会变成 1,在下一次循环的时候,就会把 3 跳过,所以需要逆序。

10
class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        for i in nums[:]:
            if nums.count(i) != 1:
                nums.pop(nums.index(i))
        return len(nums)
12
int removeDuplicates(int* nums, int numsSize){
    int len = 0;
    /*从数组首部依序取出一个元素*/
    for (len = 0; len < numsSize; len++) {
        /*从数组取出的一个元素和该元素后面的元素进行比较*/
        for (int i = len + 1; i < numsSize; i ++) {
            /*若元素相同,则将后面的元素移动到数组最后索引处,后面的元素依序往前移动一位,将数组范围 -1,等同于将被比较的元素删除*/
            if (nums[len] == nums[i]) {
                for (int j = i; j < numsSize - 1; j ++) {
                    nums[j] = nums[j + 1];
                }
                numsSize --;
                /*若有相同元素,该元素继续进行比较*/
                i = len;
            }
        }
    }
    return numsSize;
}

数组为乱序也能解决问题. 编写思路

以冒泡排序法的逻辑,从头开始比较重复的元素,若元素相同,则将元素移动到最后的数组索引,并将比较的数组范围 -1。

9