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

问题

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

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

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

说明:

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

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.

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

Note:

1. You must do this in-place without making a copy of the array.
2. 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的时间复杂度为：  ，MoveZeroes2和MoveZeroes3的时间复杂度均为： ​ 。