目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給定一個陣列 nums，撰寫一個函式將所有 0 移動到陣列的末尾，同時保持非零元素的相對順序，
示例:
輸入: [0,1,0,3,12]
輸出: [1,3,12,0,0]
說明:
- 必須在原陣列上操作，不能拷貝額外的陣列，
- 盡量減少操作次數，
2、思路
(雙指標) O ( n ) O(n) O(n)
給定一個陣列 nums，要求我們將所有的 0 移動到陣列的末尾，同時保持非零元素的相對順序，
樣例：
如樣例所示，陣列nums = [0,1,0,3,12]，移動完成后變成nums = [1,3,12,0,0] ，下面來講解雙指標的做法，
我們定義兩個指標，i指標和k指標，i指標用來遍歷整個nums陣列，k指標用來放置nums陣列元素，然后將非0元素按照原有的相對順序都放置到nums陣列前面，剩下的位置都置為0，這樣我們就完成了0元素的移動，同時也保持了非0元素的相對順序，
具體程序如下：
- 1、定義兩個指標
i和k，初始化i = 0，k = 0， - 2、
i指標向后移動，遍整個nums陣列，如果nums[i] != 0，也就是說遇到了非0元素，此時我們就將nums[i]元素放置到nums[k]位置，同時k++后一位， - 3、最后將
k位置之后的元素都賦值為0，
實作細節：
遍歷陣列可以使用for(int x : nums)，這樣就少定義一個指標，代碼也顯得更加簡潔，
時間復雜度分析： O ( n ) O(n) O(n) ， n n n是陣列的長度，每個位置只被遍歷一次，
時間復雜度分析： O ( 1 ) O(1) O(1) ，只需要常數的空間存放指標變數，
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;
}
}
原題鏈接： 283. 移動零
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297127.html
標籤：java