LeetCode 283. 移動(dòng)零【c++/java詳細(xì)題解】

cnsworder 發(fā)布于2021-09-03 10:29 / 583人閱讀

摘要：盡量減少操作次數(shù)。樣例如樣例所示，數(shù)組，移動(dòng)完成后變成，下面來講解雙指針的做法。這樣我們就完成了元素的移動(dòng)，同時(shí)也保持了非元素的相對順序。

1、題目

給定一個(gè)數(shù)組 nums，編寫一個(gè)函數(shù)將所有 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對順序。

示例:

輸入: [0,1,0,3,12]輸出: [1,3,12,0,0]

說明:

必須在原數(shù)組上操作，不能拷貝額外的數(shù)組。
盡量減少操作次數(shù)。

2、思路

(雙指針) $O (n)$

給定一個(gè)數(shù)組 nums，要求我們將所有的 0 移動(dòng)到數(shù)組的末尾，同時(shí)保持非零元素的相對順序。

樣例：

如樣例所示，數(shù)組nums = [0,1,0,3,12]，移動(dòng)完成后變成nums = [1,3,12,0,0] ，下面來講解雙指針的做法。

我們定義兩個(gè)指針，i指針和k指針，i指針用來遍歷整個(gè)nums數(shù)組，k指針用來放置nums數(shù)組元素。然后將非0元素按照原有的相對順序都放置到nums數(shù)組前面，剩下的位置都置為0。這樣我們就完成了0元素的移動(dòng)，同時(shí)也保持了非0元素的相對順序。

具體過程如下：

1、定義兩個(gè)指針i和k，初始化i = 0，k = 0。
2、i指針向后移動(dòng)，遍整個(gè)nums數(shù)組，如果 nums[i] != 0，也就是說遇到了非0元素，此時(shí)我們就將nums[i]元素放置到nums[k]位置，同時(shí)k++后一位。
3、最后將k位置之后的元素都賦值為0。

實(shí)現(xiàn)細(xì)節(jié)：

遍歷數(shù)組可以使用for(int x : nums)，這樣就少定義一個(gè)指針，代碼也顯得更加簡潔。

時(shí)間復(fù)雜度分析： $O (n)$ ， $n$ 是數(shù)組的長度，每個(gè)位置只被遍歷一次。

時(shí)間復(fù)雜度分析： $O (1)$ ，只需要常數(shù)的空間存放指針變量。

3、c++代碼

class Solution {public:    void moveZeroes(vector<int>& nums) {        int k = 0;        for(int x : nums)            if(x != 0) nums[k++] = x;        while(k < nums.size())  nums[k++] = 0;            }};

4、java代碼

class Solution {    public void moveZeroes(int[] nums) {        int k = 0;        for(int x : nums)            if(x != 0) nums[k++] = x;        while(k < nums.length)  nums[k++] = 0;          }}