删除排序数组中的重复项

柔光的暖阳◎ 2021-06-10 20:38 549阅读 0赞

### ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70][] 思路： ###

1、原地删除重复数组元素，首先要找到重复元素，然后将后面的元素前移

class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums.length <=1) {
                return nums.length;
            }
            //找到重复元素
            int pre = nums[0];
            int length = nums.length;
            int cur = 0;
            for(int i = 1;i< length;i++) {
                cur = nums[i];
                if(cur == pre) {
                    //移除当前i元素
                    for(int j = i+1; j< length;j++) {
                        nums[j-1] = nums[j];
                    }
                    length--;
                    //因为i个元素删除，其余元素前移，第i个元素因为下一个元素
                    i--;
                } else {
                    pre = cur;
                }
            }
            return length;
            
        }
    }

因为数组的长度一旦定义了就无法缩小，所以我们通过length来表示数组的长度，即使后面还有单元，我也不遍历了。  
时间复杂度O(n^2), 空间复杂度 O(1)

### 他山之石： ###

class Solution {
        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(1),不用说就比我优秀了。

其实我的代码里面每次移除元素时，后面元素都移动上来是多余的。只要定义两个数组，把不重复的元素依次放入新数组就行了。什么？不能创建新数组？好，那我就在本数组中创建新数组。i记为数组a，j记为数组b，如果数组b中元素重复，就把元素放入数组a，然后i++。最后元素的个数就是i+1个。在同一个数组中我们实现了两个数组的效果。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzk2ODYxMw_size_16_color_FFFFFF_t_70]: /images/20210518/f8dfa7135c1f4df682f29d5d997c568b.png