LeetCode Solution, Easy, 283. Move Zeroes
移動零值
Published
283. Move Zeroes
題目敘述
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
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
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
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
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
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
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
{
/**
* @param Integer[] $nums
* @return NULL
*/
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
{
/**
* @param Integer[] $nums
* @return NULL
*/
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
{
/**
* @param Integer[] $nums
* @return NULL
*/
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)
# Count the zeroes
num_zeroes = 0
for i in range(n):
num_zeroes += nums[i] == 0
# Make all the non-zero elements retain their original order.
ans = list()
for num in nums:
if num != 0:
ans.append(num)
# Move all zeroes to the end
while num_zeroes > 0:
ans.append(0)
num_zeroes -= 1
# Combine the result
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
# If the current element is not 0, then we need to
# append it just in front of last non 0 element we found.
for num in nums:
if num != 0:
nums[last_non_zero_found_at] = num
last_non_zero_found_at += 1
# After we have finished processing new elements,
# all the non-zero elements are already at beginning of array.
# We just need to fill remaining array with 0's.
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
}
}
}
}