题目:

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

示例:

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

说明:

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

思路1:

统计0元素的个数。

遍历数组,并用一个变量zeroes记录0元素的个数,遇到0元素zeroes就加1,遇到非零元素就前移zeroes个位置,最后把数组末尾的zeroes个位置填入0即可。

#include <stdio.h>

void moveZeroes(int* nums, int numsSize) {
    int i, zeros = 0;
    for (i=0; i<numsSize; i++) {
        if (nums[i] != 0) {
            nums[i-zeros] = nums[i];
        }
        else {
            zeros++;
        }
    }
    i = numsSize - zeros;
    while (i < numsSize) {
        nums[i] = 0;
        i++;
    }
}

int main()
{
    int nums[5] = {0, 1, 0, 3, 12};
    moveZeroes(nums, 5);
    for (int i=0; i<5; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

结果:

这种方法只需遍历一遍数组即可,时间复杂度O(n)。


思路2:

第2种方法很有意思。将数组分为三段,第1段是已经遍历过且不是0的元素,第2段全是0元素,第3段是还未遍历的元素。

设有两个变量i和j,i指向第3段(未遍历段)的第1个元素,j指向第2段(0元素段)的第1个元素。

若i指向的元素为0元素,则将第2段(0元素段)的右边界拓展一个位置;

若i指向的元素不为0,则将i和j指向的元素交换,然后将第2段(0元素段)和第3段(未遍历段)的右边界同时拓展一个位置。

这样依然保持  第1段是已经遍历过且不是0的元素,第2段全是0元素,第3段是还未遍历的元素  的状态。直到遍历完数组结束。

#include <stdio.h>

void moveZeroes(int* nums, int numsSize) {
    int i, j = 0, temp;
    for (i=0; i<numsSize; i++) {
        if (nums[i] != 0) {
            temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            j++;
        }
    }
}

int main()
{
    int nums[5] = {0, 1, 0, 3, 12};
    moveZeroes(nums, 5);
    for (int i=0; i<5; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

结果:

这种方法同样是遍历了一遍数组,时间复杂度也是O(n)。


第二种方法的思想还可以用在快速排序中:

#include <stdio.h>

int partition(int* nums, int Left, int Rigth) {
    int pivot = nums[Rigth];
    int i, j = Left, temp;
    for (i=Left; i<Rigth; i++) {
        if (nums[i] < pivot) {
            temp = nums[j];
            nums[j] = nums[i];
            nums[i] = temp;
            j++;
        }
    }
    temp = nums[j];
    nums[j] = nums[Rigth];
    nums[Rigth] = temp;
    return j;
}

void quickSort(int* nums, int Left, int Rigth) {
    if (Left < Rigth) {
        int Mid = partition(nums, Left, Rigth);
        quickSort(nums, Left, Mid-1);
        quickSort(nums, Mid+1, Rigth);
    }
}

int main()
{
    int nums[] = {6, 7, 3, 5, 9, 4};
    quickSort(nums, 0, 5);
    for (int i=0; i<6; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");
    return 0;
}

参考:【一起玩算法】把所有相同数字后移

推荐一位干货up主:正月点灯笼