ARTS leetcode4 Remove Element

左手的ㄟ右手 2022-02-23 14:21 97阅读 0赞

Given an array nums and a value val, remove all instances of that value in-place 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.
    
    The order of elements can be changed. It doesn't matter what you leave beyond the new length.
    
    Example 1:
    
    Given nums = [3,2,2,3], val = 3,
    
    Your function should return length = 2, with the first two elements of nums being 2.
    
    It doesn't matter what you leave beyond the returned length.
    Example 2:
    
    Given nums = [0,1,2,2,3,0,4,2], val = 2,
    
    Your function should return length = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
    
    Note that the order of those five elements can be arbitrary.
    
    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 = removeElement(nums, val);
    
    // 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]);
    }

从数组中删除指定的元素，然后返回删除后的数组的长度，特别需要注意的是，不要为另一个数组分配额外的空间，必须通过使用O（1）额外内存修改输入数组来实现此目的。（后面半句话是重点）

我的思路：  
1.判断数组不为空的情况下循环数组  
2.定义一个变量k，初始化为0，当循环数组的时候，发现数组元素与val的值不相等的时候，便把该值赋值给nums\[k\]，k是从0开始的  
3.k++，最后循环结束，返回k的值就是删除指定元素后的数组长度。  
这样做就没有重新创建数组来占用内存保留未删除的元素，而是用原来数组来保存，将元素值进行覆盖就行。只需一次遍历。

我的解法如下：

class Solution {
        public int removeElement(int[] nums, int val) {
             int k = 0;
             if(nums!=null && nums.length>0){
    	    	   for(int i=0;i<nums.length;i++){
                       if(nums[i]!= val){
                           nums[k] = nums[i];
                           k++;
                       }
                   }
    	       }
            return k;
        }
    }

下面这种解法是我看leetcode discuss中java vote最多的一个解法：

class Solution {
        public int removeElement(int[] nums, int val) {
            int l = nums.length;
            for (int i=0; i<l; i++) {
                if (nums[i] == val) {
                    nums[i--] = nums[l-- -1];
                }
            }
            return l;
        }
    }

我先说一下这个大佬的思路，看代码很简洁，但是中间if判断里面的内容不好理解。。。我想了半天，才看懂  
也是循环一次数组，从前向后遍历一次，如果有指定值和数组元素值相等，那么就把该数组的最后一个元素移动到当前数组元素的位置，  
然后数组的长度自减。这样的话，数组有几个相等的元素，那么就有数组的长度-1，然后在自减几次，最后l的值，就是数组中剩余元元素的个数。

nums[i--] = nums[l-- -1];
    //等价于下面这种
    nums[i] = nums[l-1];
    i--;
    l--;

大佬都喜欢用最简短的代码来表达 ，哈哈哈，但是可读性我觉得有点不好容易理解，尤其是应用在项目中，没有注释的话，基本会对于刚维护的人来说，有点困难。

![在这里插入图片描述][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/20220223/9516ecf8c56244928b8ac62b7e493890.png