LeetCode演算法題-Move Zeroes（Java實現-三種解法）
摘要：
這是悅樂書的第201
次更新，第211
篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第67題（順位題號是283）。給定一個數組nums，寫一個函式將所有0移動到它的末尾，同時保持非零元素的相對順序。例如：
...
這是悅樂書的第201 次更新，第211 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第67題（順位題號是283）。給定一個數組nums，寫一個函式將所有0移動到它的末尾，同時保持非零元素的相對順序。例如：
輸入：[0,1,0,3,12]
輸出：[1,3,12,0,0]
注意：
-
您必須在不製作陣列副本的情況下就地執行此操作。
-
最小化操作總數。
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 第一種解法
藉助一個新陣列和計數變數count，將不為0的數先存入新陣列，然後將新陣列中前count位賦值給陣列的對應位，再將剩下的全賦值為0即可。
此解法的時間複雜度是O(n)，空間複雜度是O(n)。
public void moveZeroes(int[] nums) {
if (nums == null || nums.length == 0) {
return ;
}
int[] newnums = new int[nums.length];
int count = 0;
for (int i=0; i<nums.length; i++) {
if (nums[i] != 0) {
newnums[count] = nums[i];
count++;
}
}
for (int j=0; j<nums.length; j++) {
if (j < count) {
nums[j] = newnums[j];
} else {
nums[j] = 0;
}
}
}
03 第二種解法
借用氣泡排序的思路，如果當前元素不等於0，就與前面的元素進行交換，這其中要藉助一個變數指標來幫助我們完成交換的工作。
此解法的時間複雜度是O(n)，空間複雜度是O(1)。
public void moveZeroes2(int[] nums) {
if (nums == null || nums.length == 0) {
return ;
}
int index = 0;
for(int i=0; i < nums.length; i++) {
if (nums[i] != 0) {
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
index++;
}
}
}
04 第三種解法
我們可以先將不等於0的元素放到陣列的前面，這需要藉助一個區域性變數，一個從0開始的指標。然後再將剩下索引所對應的元素全部賦值為0。
此解法的時間複雜度是O(n)，空間複雜度是O(1)。
public void moveZeroes3(int[] nums) {
if (nums == null || nums.length == 0) {
return ;
}
int index = 0;
for (int num : nums) {
if (num != 0) {
nums[index++] = num;
}
}
for (int i=index; i<nums.length; i++) {
nums[i] = 0;
}
}
05 小結
演算法專題目前已連續日更超過一個月，演算法題文章67 +篇，公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！