LeetCode—— 移动零

题目描述

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

示例:

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

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

一、CPP

1. 双指针法：

解题思路:使用两个指针，指针 i 负责遍历数组，指针 j 负责其后的元素均不为0。当指针 i 处的元素不为0时，才与 j 处的元素交换。
时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {

        int j = -1;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != 0){    
                j++;
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }

        for(int i=0;i<nums.size();i++){
            cout<<nums[i];
        }
        
    }
};

• 注意：当数组为[1,2,3,4,...,n,0]时，上面的算法需要做了n次相同下标的交换操作，这是没有必要的，可以增加一个进行交换的条件，只有在nums[j] ==0时才进行交换。如下：

if(nums[i] != 0){
      j++;
      //也可以用if(i!=j)
      if(nums[j] ==0){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
      }             
}

2. 单指针覆盖法：

解题思路:和双指针思想类似。不同点在于单指针的 i 总是比 j 快，当 i 不为0时总是覆盖 j 位置的数，最后再在末尾补0。
时间复杂度:O(n)。
空间复杂度:O(1)。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {

        int length = nums.size();
        int j = 0;

        for(int i : nums){
            if(i != 0){
                nums[j++] = i;
            }
        }
        //补0
        while(j<length){
            nums[j++] =0;
        }
        
    }
};

3. 辅助数组法：

解题思路:先计算0的个数，然后把不为0的数复制到辅助数组中，最后补上0的个数。然后把辅助数组的值赋值给原数组。
时间复杂度:O(n)。
空间复杂度:O(n)。题目要求在原数组上进行操作，不合题意。

class Solution {
public:

    void moveZeroes(vector<int>& nums) {
            int n = nums.size();

            // Count the zeroes
            int numZeroes = 0;
            for (int i = 0; i < n; i++) {
                numZeroes += (nums[i] == 0);
            }

            // Make all the non-zero elements retain their original order.
            vector<int> ans;
            for (int i = 0; i < n; i++) {
                if (nums[i] != 0) {
                    ans.push_back(nums[i]);
                }
            }

            // Move all zeroes to the end
            while (numZeroes--) {
                ans.push_back(0);
            }

            // Combine the result
            for (int i = 0; i < n; i++) {
                nums[i] = ans[i];
            }
        }

};

---

！！! 错误的做法：

解题思路:遍历数组，当遇到0时把其向后移动。这种方法的时间复杂度比较高，而且对于[1,2,8,0,0,7,4]的测试用例也行不通。
时间复杂度:O(n²)。
空间复杂度:O(1)

#include <iostream>
#include <vector>
using namespace std;

int main()
{   int nums [] ={1,2,8,0,0,7,4};

    int length = sizeof(nums)/sizeof(nums[0]);
    int right = length;
    int tmp;

    for(int i=0;i<length;i++){
        if(nums[i] == 0){
            for(int j = i;j<right;j++){
                tmp = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = tmp;
            }
            right--;
            
        }
    }

    for(int i=0;i<length;i++){
        cout<<nums[i];
    }
    return 0;
}

二、Java（双指针法）

class Solution {
    public void moveZeroes(int[] nums) {

        int j = -1;

        for(int i = 0;i<nums.length;i++){
            
            //等于0时直接移动i，j不动
            if(nums[i]!= 0){
                j++;
                //如果i,j指向的不是同一个
                if(i != j){
                    int tmp = nums[j];
                    nums[j] = nums[i];
                    nums[i] = tmp;
                }
            }          
        }    

    
    }
}

三、Python（双指针法）

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        j = -1

        for i in range(len(nums)):
            if nums[i] != 0:
                # python不可以j++
                j += 1;
                if i!=j:
                    nums[i],nums[j] = nums[j],nums[i]

四、各语言及算法时间复杂度

各语言及算法时间复杂度