LeetCode日记–27. Remove Element

发布于 2020-09-17  116 次阅读


碎碎念时间:

今天没咋睡够,做一道easy做了半天。不过算法题会越做越兴奋倒是真的。嘻嘻,瞬间不困了,甚至觉得可以开一把文明战到天亮:)

PS 因为发烧落下了好几篇LeetCode日记,尽量赶尽量赶。

题目如下:

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.

本人思路:

非常感人的一幕发生了:我的思路第一次赶上了LeetCode官方题解的最优解。(但是代码整了半天还是有问题最后参考了官方代码才整出来)

其实这题和昨天那道移除排序数组中的重复字符思路有些类似。都是双指针,但是如果使用的是快慢指针的方法则会增大最大遍历次数(2n次),因此这里选择使用前后两端指针向中间遍历的方法(总共n次)。

奇怪的示意图增加了!.jpg

我自己的(未能完成debug的)啥b代码如下:

public int removeElement(int[] nums, int val) {
        int temp;
        int leftPointer = 0;
        int rightPointer = nums.length - 1;
        if(rightPointer==leftPointer){
            if(nums[rightPointer]==val)
                return 0;
            else
                return 1;
        }
        for(;leftPointer<=rightPointer-1;leftPointer++){
            while(nums[rightPointer]==val&&(rightPointer+1)>0)
                rightPointer--;
            if(nums[leftPointer]==val){
                temp=nums[leftPointer];
                nums[leftPointer] = nums[rightPointer];
                nums[rightPointer] = temp;
            }
        }
        return leftPointer;
    }

官方大佬的优雅代码如下:

public int removeElement(int[] nums, int val) {
    int i = 0;
    int n = nums.length;
    while (i < n) {
        if (nums[i] == val) {
            nums[i] = nums[n - 1];
            // reduce array size by one
            n--;
        } else {
            i++;
        }
    }
    return n;
}

作者:LeetCode
链接:https://leetcode-cn.com/problems/remove-element/solution/yi-chu-yuan-su-by-leetcode/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

复杂度分析:

时间复杂度是O(n),空间复杂度是O(1)。

一些感想:

其实现在想想我的代码有个很大的问题就是一次循环想要把指针移动多位,但是事实上这样并不能减少空间/时间复杂度,反而让代码更加难懂,晦涩,增加了debug的难度,对特殊情况的兼容性也很差。


你好哇!欢迎来到雷公马碎碎念的地方:)