題目敘述
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 <= 10**4-2**31 <= nums[i] <= 2**31 - 1
Follow up: Could you minimize the total number of operations done?
Hint 1
In-place means we should not be allocating any space for extra array. But we are allowed to modify the existing array. However, as a first step, try coming up with a solution that makes use of additional space. For this problem as well, first apply the idea discussed using an additional array and the in-place solution will pop up eventually.
Hint 2
A two-pointer approach could be helpful here. The idea would be to have one pointer for iterating the array and another pointer that just works on the non-zero elements of the array.
題目翻譯
有個整數陣列 nums，需要將其中為 0 的元素往後挪移。而其他非 0 的數值需要保持其排序。必須使用 In-place 的方式來解答，可以嘗試利用 two-pointer 來降低複雜度。
解法解析
官方提供了三種解法，當然解法不止這三種，不同語言也有不同的特性或語法糖可以使用。可以各自變化，這邊只是解釋三種解法的解題思路。
Space Sub-Optimal
分成幾個步驟：
- 先用一層迴圈找出
0 的數量 numZeroes。O(n)
- 跑一層迴圈只出非
0 的元素，放到另一個陣列 arr。Worest case：O(n) 全部都非 0
- 跑一層迴圈將在第一步驟求出的
0 數量，放到 arr 中。Worest case：O(n) 全部都是 0
- 將
arr 的值都轉換到 nums。O(n)
時間複雜度：O(n)，O(4n) => O(n)
空間複雜度：O(n)
Space Optimal, Operation Sub-Optimal
使用 two-pointer 的方式，一個去記上次 0 值的位置，一個是目前遍歷的索引位置。
- 第一個迴圈將所有的非
0 值往前放，用 lastNonZeroFoundAt 紀錄目前最後出現的 0 在哪個位置。
- 從
lastNonZeroFoundAt 的位置到結尾都直接設定為 0
時間複雜度：O(n)
空間複雜度：O(1)
Optimal
這題跟上一個解法的 two-pointer 概念相同，只是這邊利用 Swap 的方式，將兩個迴圈合併成一個。
時間複雜度：O(n)
空間複雜度：O(1)
解法範例
Go
Space Sub-Optimal
func moveZeroes(nums []int) {
var n, numZeroes int = len(nums), 0
for i := 0; i < n; i++ {
if nums[i] == 0 {
numZeroes++
}
}
var ans []int
for _, num := range nums {
if num != 0 {
ans = append(ans, num)
}
}
for numZeroes > 0 {
ans = append(ans, 0)
numZeroes--
}
for i := 0; i < n; i++ {
nums[i] = ans[i]
}
}
Space Optimal, Operation Sub-Optimal
func moveZeroes(nums []int) {
var lastNonZeroFoundAt int = 0
for i := 0; i < len(nums); i++ {
if nums[i] != 0 {
nums[lastNonZeroFoundAt] = nums[i]
lastNonZeroFoundAt++
}
}
for i := lastNonZeroFoundAt; i < len(nums); i++ {
nums[i] = 0
}
}
Optimal
func moveZeroes(nums []int) {
var lastNonZeroFoundAt int = 0
for i, num := range nums {
if num != 0 {
nums[lastNonZeroFoundAt], nums[i] = num, nums[lastNonZeroFoundAt]
lastNonZeroFoundAt++
}
}
}
JavaScript
Space Sub-Optimal
var moveZeroes = function (nums) {
const n = nums.length;
let numZeroes = 0;
for (let i = 0; i < n; i++) {
numZeroes += nums[i] === 0 ? 1 : 0;
}
const ans = [];
for (const num of nums) {
if (num !== 0) {
ans.push(num);
}
}
while (numZeroes--) {
ans.push(0);
}
nums.splice(0, nums.length, ...ans);
};
Space Optimal, Operation Sub-Optimal
var moveZeroes = function (nums) {
let lastNonZeroFoundAt = 0;
for (const num of nums) {
if (num !== 0) {
nums[lastNonZeroFoundAt++] = num;
}
}
while (lastNonZeroFoundAt < nums.length) {
nums[lastNonZeroFoundAt++] = 0;
}
};
Optimal
var moveZeroes = function (nums) {
let lastNonZeroFoundAt = 0;
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
[nums[lastNonZeroFoundAt], nums[i]] = [nums[i], nums[lastNonZeroFoundAt]];
lastNonZeroFoundAt++;
}
}
};
Kotlin
Space Sub-Optimal
Kotlin 的 Array 太多樣了，不太熟悉，所以就沒寫了
Space Optimal, Operation Sub-Optimal
class Solution {
fun moveZeroes(nums: IntArray): Unit {
var lastNonZeroFoundAt = 0
for (num in nums) {
if (num != 0) {
nums[lastNonZeroFoundAt++] = num
}
}
for (i in lastNonZeroFoundAt until nums.size) {
nums[i] = 0
}
}
}
Optimal
class Solution {
fun moveZeroes(nums: IntArray): Unit {
var lastNonZeroFoundAt: Int = 0
for (i in nums.indices) {
if (nums[i] != 0) {
nums[lastNonZeroFoundAt] = nums[i].also { nums[i] = nums[lastNonZeroFoundAt] }
lastNonZeroFoundAt++
}
}
}
}
PHP
Space Sub-Optimal
class Solution
{
function moveZeroes(&$nums)
{
$n = count($nums);
$numZeroes = 0;
for ($i = 0; $i < $n; $i++) {
if ($nums[$i] == 0) {
$numZeroes++;
}
}
$ans = array();
foreach ($nums as $num) {
if ($num != 0) {
$ans[] = $num;
}
}
while ($numZeroes > 0) {
$ans[] = 0;
$numZeroes--;
}
for ($i = 0; $i < $n; $i++) {
$nums[$i] = $ans[$i];
}
}
}
Space Optimal, Operation Sub-Optimal
class Solution
{
function moveZeroes(&$nums)
{
$lastNonZeroFoundAt = 0;
foreach($nums as $num) {
if ($num != 0) {
$nums[$lastNonZeroFoundAt++] = $num;
}
}
while ($lastNonZeroFoundAt < count($nums)) {
$nums[$lastNonZeroFoundAt++] = 0;
}
}
}
Optimal
class Solution
{
function moveZeroes(&$nums)
{
$lastNonZeroFoundAt = 0;
for ($i = 0; $i < count($nums); $i++) {
if ($nums[$i] != 0) {
$tmp = $nums[$lastNonZeroFoundAt];
$nums[$lastNonZeroFoundAt] = $nums[$i];
$nums[$i] = $tmp;
$lastNonZeroFoundAt++;
}
}
}
}
Python
Space Sub-Optimal
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
num_zeroes = 0
for i in range(n):
num_zeroes += nums[i] == 0
ans = list()
for num in nums:
if num != 0:
ans.append(num)
while num_zeroes > 0:
ans.append(0)
num_zeroes -= 1
for i in range(n):
nums[i] = ans[i]
Space Optimal, Operation Sub-Optimal
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
last_non_zero_found_at = 0
for num in nums:
if num != 0:
nums[last_non_zero_found_at] = num
last_non_zero_found_at += 1
for i in range(last_non_zero_found_at, len(nums)):
nums[i] = 0
Optimal
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
last_non_zero_found_at = 0
for (i, num) in enumerate(nums):
if num != 0:
nums[last_non_zero_found_at], nums[i] = (
nums[i],
nums[last_non_zero_found_at],
)
last_non_zero_found_at += 1
Rust
Swift
Space Sub-Optimal
class Solution {
func moveZeroes(_ nums: inout [Int]) {
let n: Int = nums.count
var numZeroes: Int = 0
for i in 0..<n {
if nums[i] == 0 {
numZeroes += 1
}
}
var ans: [Int] = []
for num in nums {
if num != 0 {
ans.append(num)
}
}
while numZeroes > 0 {
ans.append(0)
numZeroes -= 1
}
nums = ans
}
}
Space Optimal, Operation Sub-Optimal
class Solution {
func moveZeroes(_ nums: inout [Int]) {
var lastNonZeroIndex: Int = 0
for num in nums {
if num != 0 {
nums[lastNonZeroIndex] = num
lastNonZeroIndex += 1
}
}
while lastNonZeroIndex < nums.count {
nums[lastNonZeroIndex] = 0
lastNonZeroIndex += 1
}
}
}
Optimal
class Solution {
func moveZeroes(_ nums: inout [Int]) {
var lastNonZeroIndex: Int = 0
for (i, num) in nums.enumerated() {
if num != 0 {
let tmp = nums[lastNonZeroIndex]
nums[lastNonZeroIndex] = num
nums[i] = tmp
lastNonZeroIndex += 1
}
}
}
}