LeetCode——283.移动0【双指针】

leetcode——283.移动 0

• 问题描述
• • 示例
• 代码
• • 方法一 循环遍历法（C）
  • 方法二 双指针法
  • • C语言
    • C++
    • Python3

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

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/move-zeroes

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

输入: nums = [0]
输出: [0]

将所有非0数放在数组的前端，后面相应补0，
i作为下标遍历原数组，j用于表示非0数在原数组的下标，初始i和j都为0
    0  1  0  3  12
    i
    j

    0  1  0  3  12
       i
    j

    1  1  0  3  12
       i
    j                nums[j] = nums[i]

    1  1  0  3  12
       i
       j             j++后j的位置

    1  1  0  3  12
             i
       j             i++寻找非0数
    
    1  3  0  3  12
             i
       j             nums[j] = nums[i]

    1  3  0  3  12
             i
          j          j++后j的位置

    1  3  0  3  12
                 i
          j          

    1  3  12  3  12
                 i
          j          nums[j] = nums[i]

    1  3  12  3  12
                 i
              j      j++后j的位置

    1  3  12  0  12
                 
              j      i遍历完成，从j开始的第1个元素置为0

    1  3  12  0  0
                 
                 j   从j开始的下1个元素设置为0，j已经到数组末尾，结束。

void moveZeroes(int* nums, int numsSize){
    int j = 0;
    for (int i = 0; i <= numsSize -1; i++) {
        // 找到非零数放在数组前端
        if (nums[i] != 0) {
            nums[j] = nums[i];
            j++;
        }
    }

    // 从j开始到数组末端全赋值0（j之前都是非0数）
    while (j <= numsSize-1) {
        nums[j++] = 0;
    }
}

双指针法（i代表右指针，j代表左指针）
    0  1  0  3  12
    i
    j

    0  1  0  3  12     i指向数组第1个非零数，准备交换nums[i]和nums[j]，即准备交换1和0
       i
    j

    1  0  0  3  12
       i               swap(&nums[i], &nums[j])交换，即1和0交换完成（第1轮交换）
    j

    1  0  0  3  12
             i         i移动到下一个非0数字，j向前移动1步，准备交换nums[i]和nums[j]，即准备交换3和0
       j

    1  3  0  0  12
             i         swap(&nums[i], &nums[j])交换，即3和0交换完成（第2轮交换）
       j

    1  3  0  0  12
                 i     i移动到下一个非0数字（刚好是数组结尾），j向前移动1步，准备交换nums[i]和nums[j]，即准备交换12和0
          j

    1  3  12  0  0
                 i     swap(&nums[i], &nums[j])交换，即12和0交换完成（第3轮交换）。由于i已经到达数组结尾，因此结束。
           j

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void moveZeroes(int* nums, int numsSize) {
    int j = 0;
    for (int i = 0; i <= numsSize -1; i++) {
        if (nums[i] != 0) {
            swap(&nums[i], &nums[j]); // 交换数组下标索引i和j对应的元素值
            j++;  // 左指针右移1步
        }
    }
}

class Solution {
public:
    void moveZeroes(vector& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        n = len(nums)
        left = right = 0
        while right < n:
            if nums[right] != 0:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
            right += 1