ARTS leetcode8 Remove Duplicates from Sorted Array

淡淡的烟草味﹌ 2022-04-25 05:52 59阅读 0赞

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]);
    }

给定排序的数组nums，就地删除重复项，使每个元素只出现一次并返回新的长度。

不要为另一个数组分配额外的空间，必须通过使用O（1）额外内存修改输入数组来实现此目的。

这个题的特别之处就在于不能创建另外的数组或者数据结构来存储值，只可以通过修改原来数组的值，来进行返回。

思路：该元素和之前的一个元素的大小做比较，如果不相等，则用一个变量计数加一，并且将该元素赋值给下标为0的元素，以此类推，否则什么否不做；此时有一个问题，就是第一个元素会被忽略掉，所以需要设定一个特殊的值，当元数组前几个元素都是一样的时候，这样计数值也可以加1，那么当遇到第二个不一样的值的时候，就和上面一样开始进行判断循环。

class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int count  = 0;
            int index = 0;
            int len = nums.length-1;
            int temp = Integer.MAX_VALUE;
            for(int i=0;i<=len;i++){
                if(nums[i]!= temp){
                    count++;
                    nums[index++] = nums[i];
                    temp = nums[i];
                }
            }
            
            return count;
        }
    }

Runtime: 1 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted Array.
    Memory Usage: 40.8 MB, less than 84.75% of Java online submissions for Remove Duplicates from Sorted Array.

下面这个解法是看discuss中的一个解法，  
（1）也是先假设一个值为第一个元素值，  
（2）然后让数组中的每个元素与假设的值做大小比较  
（3）如果两个元素值不相等，则对Index++，并且将数组中该元素的值赋给假设的temp，同时也将该值赋给下标为index的数组元素。

class Solution {
        public int removeDuplicates(int[] nums) {
            if(nums == null || nums.length == 0){
                return 0;
            }
            int index = 0;
            int len = nums.length-1;
            int temp = nums[0];
            for(int i=0;i<=len;i++){
                if(nums[i]!= temp){
                     temp = nums[i];
                     index++;
                    nums[index] = nums[i];
                }
            }
            return index+1;
        }
    }

Runtime: 1 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted Array.
    Memory Usage: 40.6 MB, less than 85.51% of Java online submissions for Remove Duplicates from Sorted Array.

下面这种解法是leetcode discuss中vote 最多的一种，这个解题思路有点特别，第一次看的话，看不出来为什么return i,最后举了个demo，跟着每步走了一下，才发现了是如何执行的。他的思路：  
（1）先给i设定一个初始值，如果nums长度大于0，则设定为1，否则设定为0  
（2）如果为i设定为0，那么就直接返回0，否则就开始循环数组中的每个元素  
（3）为什么这个大佬在nums.length>0的时候设定i的值为1，看里面的if判断可以明白，  
如果设定为1，那么从数组第一个元素开始与数组的第一个元素的大小做比较，  
如果数组中的元素大于第0个元素，也就是说两个元素不一样，那么就会把该元素的值 赋给num\[1\]，并且i++，否则，  
如果数组的下一个元素与nums\[i-1\]相等，什么也不做，继续下一次循环，直到数组中所有元素循环完毕。  
最后返回的i的数值就是数组中非重复的元素个数。

如果你自己走一遍程序，作者也就是通过一次循环和if判断，逐渐将不同的元素一步一步的赋值到前面的元素。

class Solution {
        public int removeDuplicates(int[] nums) {
            int i = nums.length > 0 ? 1 : 0;
            for (int n : nums)
                if (n > nums[i-1])
                    nums[i++] = n;
            return i;
        }
    }

Runtime: 1 ms, faster than 100.00% of Java online submissions for Remove Duplicates from Sorted Array.
    Memory Usage: 42.3 MB, less than 28.49% of Java online submissions for Remove Duplicates from Sorted Array.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTI5MzQzMjU_size_16_color_FFFFFF_t_70]: /images/20220205/57fa61e5a3444498819fbefa401d8ea6.png