Easy題。把陣列中的0往後移，其餘非0值維持原來的順序。解題時不可複製到新陣列，必須在同陣列中操作。
題目
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]
Example 2:
Input: nums = [0]
Output: [0]
Constraints:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1
先想到的解法
直覺想到用迴圈從頭往後一個一個檢查，如果是0則用另一個迴圈檢查後面是否有非0的值，若有則倆倆互換。內外兩廽圈時間複雜度O(n^2)，沒產生新陣列空間複雜度O(1)。
nums=[0,1,0,3,12]
==============================outter:L1, inner:L1=============================
v(i=0)
nums=[0,1,0,3,12]
^(j=i)
==============================outter:L1, inner:L2=============================
v(i=0)
nums=[0,1,0,3,12]
^(j=i+1)
swap nums[i] and nums[j]
v(i=0)
nums=[1,0,0,3,12]
^(j=i+1)
==============================outter:L2, inner:L1=============================
v(i=1)
nums=[1,0,0,3,12]
^(j=i)
==============================outter:L2, inner:L2=============================
v(i=1)
nums=[1,0,0,3,12]
^(j=i+1)
==============================outter:L2, inner:L3=============================
v(i=1)
nums=[1,0,0,3,12]
^(j=i+2)
swap nums[i] and nums[j]
v(i=1)
nums=[1,3,0,0,12]
^(j=i+2)
==============================outter:L3, inner:L1=============================
v(i=2)
nums=[1,3,0,0,12]
^(j=i)
==============================outter:L3, inner:L2=============================
v(i=2)
nums=[1,3,0,0,12]
^(j=i+1)
==============================outter:L3, inner:L3=============================
v(i=2)
nums=[1,3,0,0,12]
^(j=i+2)
swap nums[i] and nums[j]
v(i=2)
nums=[1,3,12,0,0]
^(j=i+2)
Main.java
package com.abc.demo;
import java.util.Arrays;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
}
public static int[] moveZeroes(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
for (int j = i; j < nums.length; j++) {
if (nums[j] != 0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
break;
}
}
}
}
return nums;
}
}
在LeetCode上提交後效能排名很後面，代表有更加解法。
更加解 一
用迴圈遍歷陣列及用一個佇列(queue)來記住元素0的索引。當遍歷到下次非0元素時將目前元素值放到queue中最前的索引位置，而目前元素值改為0。時間複雜度O(n)；用了一個最大同陣列長度的queue，空間複雜度O(n)。
nums=[0,1,0,3,12]
============================L1=============================
v(i=0)
nums=[0,1,0,3,12]
q=[0]
============================L2=============================
v(i=1)
nums=[0,1,0,3,12]
q=[0]
num[0] = num[i]
set num[i] = 0
q=[]
v(i=1)
nums=[1,0,0,3,12]
q=[1]
============================L3=============================
v(i=2)
nums=[1,0,0,3,12]
q=[2,1]
============================L4=============================
v(i=3)
nums=[1,0,0,3,12]
q=[2,1]
num[1] = num[i]
set num[i] = 0
q=[2]
v(i=3)
nums=[1,3,0,0,12]
q=[3,2]
============================L5=============================
v(i=4)
nums=[1,3,0,0,12]
q=[3,2]
num[2] = num[i]
set num[i] = 0
q[3]
v(i=4)
nums=[1,3,12,0,0]
q=[4,3]
Main.java
package com.abc.demo;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
}
public static int[] moveZeroes(int[] nums) {
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
q.add(i);
}
if (nums[i] != 0) {
if (q.isEmpty()) {
continue;
}
nums[q.poll()] = nums[i];
nums[i] = 0;
q.add(i);
}
}
return nums;
}
}
更加解 二
參考網路解答。用廽圈遍歷陣列並紀錄最前元素0的索引及紀錄出現0的次數。當遍歷的元素非0時將紀錄元素0的索引位置的值設為當前元素值，並累加最前元素0的索引值到結束，最後從陣列尾端往前依出現0的次數依序把後面的元素值改為0。時間複雜度兩個單迴圈O(2n)相當於O(n)，空間複雜度O(1)。
nums=[0,1,0,3,12]
============================L1=============================
v(i=0)
nums=[0,1,0,3,12]
firstZeroIndex=0
zeroCount=1
============================L2=============================
v(i=1)
nums=[0,1,0,3,12]
set nums[0] = nums[i]
v(i=1)
nums=[1,1,0,3,12]
firstZeroIndex=1
zeroCount=1
============================L3=============================
v(i=2)
nums=[1,1,0,3,12]
firstZeroIndex=1
zeroCount=2
============================L4=============================
v(i=3)
nums=[1,1,0,3,12]
set nums[1] = nums[i]
v(i=3)
nums=[1,3,0,3,12]
firstZeroIndex=2
zeroCount=2
============================L5=============================
v(i=4)
nums=[1,1,0,3,12]
set nums[2] = nums[i]
v(i=4)
nums=[1,3,12,3,12]
firstZeroIndex=3
zeroCount=2
============================Loop End=============================
Set the last 2 elements to 0
nums=[1,3,12,0,0]
Main.java
package com.abc.demo;
import java.util.Arrays;
public class Main {
public static void main(String[] arges) {
System.out.println(Arrays.toString(moveZeroes(new int[]{0, 1, 0, 3, 12})));
}
public static int[] moveZeroes(int[] nums) {
int i = 0;
int firstZeroIndex = 0; // 最前元素0的索引
int zeroCount = 0; // 紀錄元素0的出現次數
while (i < nums.length) {
if (nums[i] != 0) {
nums[firstZeroIndex] = nums[i];
firstZeroIndex++;
} else {
zeroCount++;
}
i++;
}
// 從陣列後往前依照0出現次數依序把元素值改為0
for (int j = nums.length - 1; j >= nums.length - zeroCount; j--) {
nums[j] = 0;
}
return nums;
}
}
寫完想起來兩年前去美商訊能集思駐點面試時考過這題白板題。
沒有留言:
張貼留言