元素移动

移动零

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

注意:

• 必须在原数组上操作，不能拷贝额外的数组。
• 尽量减少操作次数。

示例:

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

方案A 冒泡思想

思路:这道题数据量较小，可以使用冒泡排序的思想，将所有 0 依次交换到数组末尾。分析可知，冒泡排序不会改变本题中非零元素的相对顺序，所以符合题目中保持非零元素相对顺序的要求。

:::details 点击查看代码

function moveZeroes(nums) {
    let zeroCount=0;
    for(let i=0;i<nums.length-zeroCount;i++){
        if(nums[i]==0){
            for(let j=i;j<nums.length-zeroCount-1;j++){
                [nums[j],nums[j+1]]=[nums[j+1],nums[j]];
            }
            zeroCount++;
            i--;
        }
    }
    return nums;
};

:::

性能分析:

• 时间复杂度:
• 空间复杂度:

方案B 双指针

思路:使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质:

• 左指针左边均为非零数；
• 右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

:::details 点击查看代码

function moveZeroes(nums) {
    let len=nums.length;
    let left=0;
    let right=0;
    while(right<len){
        if(nums[right]!=0){
            [nums[left],nums[right]]=[nums[right],nums[left]];
            left++;
        }
        right++;
    }
    return nums;
};

:::

性能分析:

• 时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。

• 空间复杂度：O(1)。只需要常数的空间存放若干变量。