283. 移动零

时间:2021-2-20 作者:admin

LeetCode – 283. 移动零

题目

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

限制条件:

  1. 必须在原数组上操作,不能拷贝额外的数组。
  2. 尽量减少操作次数。

解题思路

1. 双指针二次遍历

  1. 指针 i 访问一遍数组,遇到 非0 元素时,将值赋给指针 j ,指针 j 记录 非0 元素后向后移动;
  2. 将指针 j 视为起点进行后续遍历,将后面位置的值更改为 0
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let j = 0, l = nums.length
    for (let i = 0; i < l; i++) {
        // 非零元素移至 j
        if (nums[i]) {
            nums[j] = nums[i]
            j++
        }
    }
    // 后续位置更新为 0
    for (let i = j; i < l; i++) {
        nums[i] = 0
    }
};

2. 双指针交换

  • 指针 i 、j初始指向索引 0
  • 指针 j 指向提供给非 0 项的坑位
  • 指针 i 推进找非 0 项,想交换到 j 指向的坑位
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    let i = 0, j = 0, l = nums.length
    // 指针 i 到达终点时, 所有 0 值已交换至尾部
    while (i < l) {
        if (nums[i] !== 0) {
            // 将 i 位置的 非0 元素 至 j 位置的 0 交换
            [nums[i], nums[j]] = [nums[j], nums[i]]
            // 移动指针
            i++
            j++
        } else {
            // 移动指针 i 至非 0 项, 指针 j 留在 0 值所在的位置
            i++
        }
    }
}

3. splice + push

遍历数组,遇到 0 时:

  1. 使用 splice 移除一位
  2. push 加入尾部 0
  3. 将需要到达的终点前移一位
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let l = nums.length
    for (let i = 0; i < l; i++) {
        // 遇到 0 值
        if (!nums[i]) {
            // 移除 0 值, 加入尾部
            nums.splice(i, 1)
            nums.push(0)
            // 继续访问当前索引, 前移遍历终点
            i--
            l--
        }
    }
}

4. sort 排序

  1. b 为 0 时,将 sort 函数返回值设置为 -1,交换位置
  2. b 不为 0 时,返回值设置为 0,保持非零元素的原始顺序
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    nums.sort((a, b) => b? 0: -1)
};
声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。