力扣网C语言编程题：移动零

一. 简介

本文记录力扣网上的逻辑编程题，涉及数组方面的，主要以 C语言实现。

二. 力扣网C语言编程题：移动零

题目：移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

提示:

    1 <= nums.length <= 104
    -231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

解题思路一：

1. 使用双指针，一个指针指向已处理元素的末尾，另一个指针指向未处理元素的头部；

2. 遍历数组元素，判断元素是否为0，为 0则交换左右元素的位置。

C语言实现如下：

#include <stdio.h>

void swap_data(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void moveZeroes(int* nums, int numsSize) {
    if((nums == NULL) && (!numsSize)) {
        return;
    }

    int right = 0;
    int left = 0;
    //遍历数组，当元素为非零数时交换左右元素
    while(right < numsSize) {
        if(nums[right]) {
            swap_data(nums+left, nums+right);
            left++;
        }
        right++;
    }
}

可以看出，上面的代码实现的时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路二：

1. 遍历数组，如果数组元素为非零，则将元素存入数组前面，同时统计非零元素的数目；

2. 将数组末尾写入0；

C语言实现如下：

#include <stdio.h>

void moveZeroes(int* nums, int numsSize) {
    if((nums == NULL) && (!numsSize)) {
        return;
    }
 
    int i = 0;
    int k = 0;
    //遍历数组，如果元素值为非零则放在数组前面
    for(i = 0; i < numsSize; i++) {
        if(nums[i] != 0) {
            nums[k] = nums[i];
            k++;
        }
    }
    //将数组末尾赋0
    for(i = 0; i < (numsSize-k); i++) {
        nums[k+i] = 0;
    }
}

可以看出，这种方法的时间复杂度为 O(n)，空间复杂度为 O(1)。

解题思路三：

1. 只遍历一遍数组，先将数组元素保存；然后将 nums[i] =0；

2. 如果数组元素为 非零，则依次将元素保存到数组前面部分；

C语言实现如下：

#include <stdio.h>

void moveZeroes(int* nums, int numsSize) {
    if((nums == NULL) && (!numsSize)) {
        return;
    }
 
    int i = 0;
    int k = 0;
    int tmp = 0;
    //遍历数组，如果元素值为非零则放在数组前面
    for(i = 0; i < numsSize; i++) {
        tmp = nums[i];
        nums[i] = 0;
        if(tmp != 0) {
            nums[k] = tmp;
            k++;
        }
    }
}

可以看出，其实这种方法是对思路二的一种优化方法。