C#LeetCode刷题之#283-移动零（Move Zeroes）

问题

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

说明:

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

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note:

You must do this in-place without making a copy of the array.
Minimize the total number of operations.

示例

public class Program {

    public static void Main(string[] args) {

        int[] nums = null;

        nums = new int[] { 0, 1, 0, 3, 12 };

        MoveZeroes(nums);

        ShowArray(nums);

        nums = new int[] { 0, 0, 6, 0, 18, 22, 0, 0, 5 };

        MoveZeroes2(nums);

        ShowArray(nums);

        nums = new int[] { 1, 0, 4, 0, 0, 7, 0, 9, 0 };

        MoveZeroes3(nums);

        ShowArray(nums);

        Console.ReadKey();

    }

    private static void ShowArray(int[] array) {

        foreach(var num in array) {

            Console.Write($"{num} ");

        }

        Console.WriteLine();

    }

    private static void MoveZeroes(int[] nums) {

        //在原数据中移动，有点类似于插入排序

        bool zero = false;

        for(int i = 0, count = 0; i < nums.Length - count; i++) {

            if(nums[i] == 0) {

                //记录下一个数是不是0，如果是零的话，要重新移动一次以确保所有0都被处理过

                zero = false;

                if(i + 1 < nums.Length && nums[i + 1] == 0) {

                    zero = true;

                }

                //移动数组

                for(int j = i + 1; j < nums.Length - count; j++) {

                    nums[j - 1] = nums[j];

                }

                nums[nums.Length - count - 1] = 0;

                count++;

                //移动指针，确保所有0都被处理过

                if(zero) {

                    i--;

                }

            }

        }

    }

    private static void MoveZeroes2(int[] nums) {

        //快慢双指针法

        int n = nums.Length;

        int index = 0;

        for(int i = index; i < n; i++) {

            if(nums[i] != 0) {

                Swap(ref nums[i], ref nums[index]);

                index++;

            }

        }

    }

    private static void Swap(ref int num1, ref int num2) {

        int swap = num1;

        num1 = num2;

        num2 = swap;

    }

    private static void MoveZeroes3(int[] nums) {

        //把所有不是0的移动到数组前部，余下的部分全部置0

        int index = 0;

        for(int i = 0; i < nums.Length; i++) {

            //使用index索引把所有不是0的数据移到前部

            if(nums[i] != 0)

                nums[index++] = nums[i];

        }

        //余下的部分置0

        while(index < nums.Length)

            nums[index++] = 0;

    }

}

以上给出2种算法实现，以下是这个案例的输出结果：

1 3 12 0 0

6 18 22 5 0 0 0 0 0

1 4 7 9 0 0 0 0 0

分析：

显而易见，MoveZeroes的时间复杂度为： C#LeetCode刷题之#283-移动零（Move Zeroes）-LMLPHP ，MoveZeroes2和MoveZeroes3的时间复杂度均为：。