leetcode27-移除元素

leetcode 27

方法1 暴力法

时间复杂度：O(n2) 空间复杂度：O(1)

暴力法比较简单，使用两层for循环，第一层遍历以后如果找到对应的值是val，那么进行第二层的遍历，第二层遍历从当前索引开始向后遍历，然后让每个元素向前移动一位

var removeElement = function (nums, val) {
  let k = 0;
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    if (nums[i] === val) {
      for (let j = i; j < len; j++) {
        nums[j] = nums[j + 1]
      }
      // 移动以后需要在判断一下当前这一项，所以i--
      i--;
      // 移动后总长度减少
      len--;
    } else {
      k++;
    }
  }
  return k;
}

方法2 利用js的splice方法

时间复杂度：O(n2) 空间复杂度：O(1)

循环数组，如果遇到当前值等于val的，则移除当前项，由于数组的splice方法的时间复杂度是O(n)，所以总的时间复杂是O(n2)

var removeElement = function (nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1);
    } else {
      k++
    }
  }
  return nums.length;
}

方法3 双指针-优解

时间复杂度：O(n) 空间复杂度：O(1)

利用快慢指针来实现，一次循环，将时间复杂度降为O(n)
快指针：表示最终数组中应该存放的元素
慢指针：数组该元素应该放置的下表
下面代码中的**i**表示快指针，slow表示慢指针

• 如果当前元素 nums[i] 不等于目标值 val，那么当前元素需要存放到数组nums，将其赋值到慢指针位置 nums[slow]，然后移动慢指针slow

• 如果当前元素 nums[i] 等于目标值 val，跳过它，因为val值不需要存放数组（快指针继续移动，但慢指针不动）

• 遍历完成后，慢指针 slow 的值就是新数组的长度

var removeElement = function (nums, val) {
  let slow = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      // 数组应该存放的值
      nums[slow] = nums[i];
      slow++
    }
  }
  return slow;
}

双指针不做删除操作，主要实现的是一个元素重新赋值的过程，可以假设为nums的每一项都是空的，我们要给他填充值，如果当前元素等于val，那么位置先空置，直到找到了可以放置的元素(!==val)，再填充到当前位置(slow)上，这个位置填充以后呢，需要走到下一个位置去，所以slow++

以上就是这道题的三种解答方法啦，当然除了这些，还有很多其他的方法可以解答，欢迎大家多多分享～

原文地址：https://blog.csdn.net/weixin_45799371/article/details/145159607

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！