阅读 522

LeetCode 27. 移除元素:JavaScript 遍历和双指针两种解法

题目链接leetcode-cn.com/problems/re…

方法一

解题思路

  • 主要思路是遍历数组 nums,每次取出的数组元素为 num,设置初始下标为 ans
  • 在遍历过程中,如果 num 与需要移除的值不同,则进行拷贝覆盖 nums[ans] = numans 自增 1。
  • 如果相同,则跳过该数字不进行拷贝覆盖,最后 ans 即为新的数组长度。
  • 这种思路适用于需要移除的元素较多时,最极端的情况是全部元素都需要移除,遍历一遍结束即可。

代码

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let ans = 0;
    for (const num of nums) {
        if (num != val) {
            nums[ans] = num;
            ans++;
        }
    }
    return ans;
};
复制代码

复杂度分析:

  • 时间复杂度:{O}(n)
  • 空间复杂度:{O}(1)

方法二

解题思路

现在考虑数组包含很少的要删除的元素的情况。例如,num = [1, 2, 3, 5, 4]val = 4。之前的算法会对前四个元素做不必要的复制操作。另一个例子是 num = [4, 1, 2, 3, 5]val = 4。似乎没有必要将 [1, 2, 3, 5] 这几个元素左移一步,因为问题描述中提到元素的顺序可以更改。

因此,我们可以这样解本题:当我们遇到 nums[i] = val 时,我们可以将当前元素与最后一个元素进行交换,并释放最后一个元素。这实际上使数组的大小减少了 1。

请注意,被交换的最后一个元素可能是你想要移除的值。但是不要担心,在下一次迭代中,我们仍然会检查这个元素。

代码

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    let ans = nums.length;
    for (i = 0; i < ans;) {
        if (nums[i] == val) {
            nums[i] = nums[ans - 1];
            ans--;
        } else {
            i++
        }
    }
    return ans;
};
复制代码

复杂度分析:

  • 时间复杂度:{O}(n)
  • 空间复杂度:{O}(1)

更多题解请关注github.com/leviding/le…


关注公众号「技术漫谈」加算法群,每天一道算法题,趣学算法很容易!:

  • LeetCode 算法题解
  • JavaScript 入门到进阶
  • 前端项目从零到一实战
  • 前端学习方法路线分享
  • ……

微信公众号