Leetcode——移動ゼロ(python,c++)

配列numsが与えられ、ゼロ以外の要素の相対的な順序を維持しながら、すべての0を配列の末尾に移動する関数が記述される.
例:
入力:[0,1,0,3,12]出力:[1,3,12,0,0]説明:
元の配列で操作する必要があります.追加の配列はコピーできません.操作回数をできるだけ減らす.
考え方:1.配列中のゼロではない数字を新しい配列に入れることができ、ゼロではないポインタインデックスを設定し、後ろに0を格納するために使用することができます.

class Solution:
    def moveZeroes(self, nums):
        k = 0			#  
        for num in nums:
            if num != 0:	#  0     nums   
                nums[k] = num
                k += 1		#    
        while k < len(nums):	# k        ，    0  
            nums[k] = 0
            k += 1

時間的複雑度はO(n)であり,空間的複雑度は一致した.

//
// Created by zdq on 2019/11/13.
//
#include
#include

using namespace std;
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int> nonZeroElements;
        // vec    0    nonZeroElements 
        for(int i = 0; i<nums.size(); i++)
            if(nums[i])
                nonZeroElements.push_back(nums[i]);
        // nonZeroElements           nums     
        for(int i = 0;i<nonZeroElements.size();i++)
            nums[i] = nonZeroElements[i];
       	// nums        0
        for(int i=nonZeroElements.size();i<nums.size();i++)
            nums[i]=0;
    }
};
//    
int main(){
    int arr[] = {0,1,0,3,12};
    vector<int> vec(arr, arr+sizeof(arr)/sizeof(int));
    Solution().moveZeroes(vec);
    for(int i=0;i<vec.size();i++)
        cout<<vec[i]<<" ";
    cout<<endl;
}

2.pythonにはpopとappendの方法があります.まず0の要素をポップアップし、配列の最後に置くといいです.

class Solution:
    def moveZeroes(self, nums):
        j=0
        for i in range(len(nums)):
            if nums[j] == 0:
                nums.append(nums.pop(j))
            else:
                j+=1

時間の複雑さもO(n)

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int k = 0; //nums ，[0..k]      0  

        //    i    ，  [0..i]    0          [0..k] 
        for(int i=0; i<nums.size();i++)
            if(nums[i])
                nums[k++] = nums[i];
        // nums       0
        for(int i = k;i<nums.size();i++)
            nums[i] = 0;
    }
};

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

        int k = 0; // nums , [0...k)      0  

        //     i    ,  [0...i]    0  
        //         [0...k) 
        //   , [k...i]   0
        for(int i = 0 ; i < nums.size() ; i ++)
            if(nums[i])
                swap(nums[k++] , nums[i]);

    }
};

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

        int k = 0; // nums , [0...k)      0  

        //     i    ,  [0...i]    0  
        //         [0...k) 
        //   , [k...i]   0
        for(int i = 0 ; i < nums.size() ; i ++)
            if(nums[i])
                if(k != i)
                    swap(nums[k++] , nums[i]);
                else
                    k ++;
    }
};