欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

删除排序数组中的重复项

程序员文章站 2024-03-16 12:54:40
...

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数,但输出的答案是数组呢?

请注意,输入数组是以“引用”方式传递的,这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说,不对实参做任何拷贝

int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。

// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。

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

  print(nums[i]);

}

这其实是我以前做过的一道题,但是昨天无聊去翻的时候发现解答很繁琐,解答如下

public int removeDuplicates(int[] nums) {
        int count = nums.length;
        int length = count;
        int i=0;
        if (count>1){
            while (i<length-1){
                if (nums[i]>nums[i+1]){
                    break;
                }
                if (nums[i]==nums[i+1]){
                    length--;
                    int temp = nums[i];
                    count--;
                    for (int j=i;j<nums.length-1;j++){
                        nums[j] = nums[j+1];
                    }
                    nums[nums.length-1] = temp;
                    i=0;
                    continue;
                }
                i++;
            }
           if(count==2){
            if (nums[0]==nums[1]){
                    return 1;
                }
        }
        } 
        return count;
    }

说实话,我都不知道我是怎么做出来的,而且还通过了…估计有打表嫌疑,所以我又重新做了一遍,这一次相比而言就要清晰明了很多了

public int removeDuplicates(int[] nums) {
        int pos = 0;
        for(int i=1;i<nums.length;i++){
            if(nums[pos]!=nums[i]){
                nums[++pos] = nums[i];
            }
        }
        return ++pos;
    }

逻辑其实很简单

  1. 如果相邻两个数相同的话就不操作
  2. 如果相邻两个数不相同的话则将进行比较的右边的数放到左边数的旁边(有点绕,我举个例子)

示例数组[1,1,2],使用如上代码逻辑(简单的那个)

  1. 比较[1,1],由于两个数相同,不进行操作,此时nums[0]=1,nums[1]=1
  2. 然后i++,nums[0]=1,nums[2]=2,两个数不同,那么执行nums[++pos] = nums[i],相当于就是nums[1]=nums[2],以此类推

总结:

  1. 数组是引用类型传递。
  2. 优化代码的感觉真爽。
相关标签: 算法 数组