14-移动零

自己的做法

算法思想

使用哈希表，首先遍历一遍数组，将所有为0 的索引存入到哈希表中，然后再遍历数组，分为两个循环，前一个从数组开头循环到(数组长度 - 哈希表长度 - 1)位置，依次将不在哈希表中的索引对应的数字，按顺序存到数组中；后一个循环从(数组长度 - 哈希表长度)位置 循环到数组末尾，全部赋值为 0 。

算法实现

class Solution {
public:
    static void moveZeroes(vector<int>& nums) {
        set<int> indexs;
        int i = 0;
        for(i = 0; i < nums.size(); i++) {
            if(nums[i] == 0) {
                indexs.insert(i);
            }
        }
        int count = 0;
        i = 0;
        while (i < nums.size() - indexs.size()){
            if(indexs.count(count) == 0) {
                nums[i] = nums[count];
                i++;
            }
            count++;
        }
        for(i = nums.size() - indexs.size(); i < nums.size(); i++) {
            nums[i] = 0;
        }
    }
};

性能分析

时间复杂度：遍历了两遍数组，为$O(n)$。

空间复杂度：使用了哈希表，为$O(n)$。

官方做法

算法思想

双指针法。

左指针指向已处理好的序列的尾部；右指针指向待处理序列的头部。当右指针指向的是非零数时，交换左右指针对应的数字，左右指针分别向后走一步；如果右指针指向的为零，则右指针向后走一步。初始时，左右指针都指向数组第一个元素。

则：

1. 左指针左边是已经处理好的序列，全部为非零数
2. 右指针左边和左指针及其右边之间的数全部是零

也就是说，左指针指向下一个需要交换的元素。右指针一直向右移动直到遇到一个不为零的数。然后交换左右指针对应的数。

算法实现

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

性能分析

时间复杂度：遍历了一遍数组，为$O(n)$。

空间复杂度：使用了两个指针，为$O(1)$。