LeetCode_双指针_简单_283.移动零

x33g5p2x  于2022-02-07 转载在 其他  
字(1.2k)|赞(0)|评价(0)|浏览(293)

1.题目

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

示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作,不能拷贝额外的数组。尽量减少操作次数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/move-zeroes

2.思路

(1)双指针1
① 定义快慢指针 slow 和 fast,其中 slow 指向当前已经处理好的序列的尾部,fast 指向待处理序列的头部。
② 初始时 slow 和 fast 均指向数组的第一个元素。然后 fast 不断向右移动,每次 fast 指向非零数时,则将 slow 和 fast 对应的数交换,同时 slow 右移。
③ 结束之后,数组中所有的 0 都移动到了末尾,同时也保持非零元素的相对顺序。
(2)双指针2
① 去除数组nums中的所有 0,并返回去除0之后的数组长度newLen(非零元素的相对顺序保持不变),这里需要复用LeetCode_双指针_简单_27.移除元素这题的代码。。
② 将数组nums中索引在newLen及之后的所有元素赋值为 0即可。

3.代码实现(Java)

//思路1————双指针1
public void moveZeroes(int[] nums) {
    int length = nums.length;
    int slow = 0,fast = 0;
    while(fast < length){
        if(nums[fast]!=0){
            //将每一个不为0的元素nums[fast]移动到数组前面,那么数组末尾的元素均为0
            swap(nums,slow,fast);
            //交换之后nums[slow]的值不为0,slow指针右移一位
            slow++;
        }
        fast++;
    }
}

//交换nums[slow]和nums[fast]的值
public void swap(int[] nums,int slow,int fast){
    int temp = nums[slow];
    nums[slow] = nums[fast];
    nums[fast] = temp;
}
//思路2————双指针2
public void moveZeroes(int[] nums) {
    //去除数组nums中的所有 0,并返回去除0之后的数组长度
    int newLen = removeElement(nums, 0);
    //将newLen之后的所有元素赋值为 0
    while(newLen < nums.length){
        nums[newLen++]=0;
    }
}

//复用 LeetCode_双指针_简单_27.移除元素 的代码
int removeElement(int[] nums, int val) {
    int fast = 0, slow = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
        fast++;
    }
    return slow;
}

相关文章