iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 26
1
Software Development

從LeetCode學演算法系列 第 26

[Day 26] 從LeetCode學演算法 - 0283. Move Zeroes (Easy)

目標:
這題主要目的在於讓讀者繼續熟悉一些陣列的常用操作及方法。

原題:

Question:
Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

分析/解題:
題目給定一個陣列nums並要求將所有當中的0全部都放到最後面,
且必須保持所有非0的元素的原有相對排列。
另外Note中還要求必須要in-place且最小化總共操作的次數。

這題其實有很多變形,雖然簡單,
務必請留意題目所要求的條件,不要倉促作答。

首先題目強調必須in-place(in-place的部分先前的文章有提到過),
故諸如開一個ArrayList/List來將所有非0的部分一個一個存起來的方法,
在這裡就完全行不通了。

直覺上或許讀者會想到諸如以下的方法:

  1. 從頭開始找到第一個0元素(位置假設為a)
  2. 找到從這個0元素以後第一個非0的元素
  3. 將兩者交換
  4. 從a+1開始找到下一個0元素
  5. 再找到從這個0元素以後第一個非0的元素
  6. 按照這樣的邏輯直到沒有更多的0元素,或找到0元素以後,
    其後沒有非0的元素為止。
    (上面的方法沒有很嚴謹,因為1有可能就已經找不到0元素了,
    僅為大概的範例)

但這樣的方法對每一個0元素都有可能需要掃瞄過一整個陣列,
總體的時間複雜度會來到O(N^2)

有更好的方法嗎?
我們可以先考慮:
如果我們將原先的陣列當成額外開的ArrayList或List來使用的話呢?
先將所有的非0值從index 0開始放入,直到沒有非0的元素為止,
接著,和開新的空間不同,後面多出來的部分相當於被排開的0
所以我們要將後面的值全部設為0

這麼做只需要記錄當前非0的部分放到哪邊,在其後再進行補0的動作即可,
最極端的狀況是全部都是0(即完全不用更動陣列),
以及全部都非0(即將原本的位置複寫相同的數字一次);
一旦中間有出現0的狀況,只代表其後的數字被往前挪一格
讀者可以紙筆稍加操作看看即可確認不會有非0的數字會被吃掉XD~

我們使用了index來記錄下一個即將被寫入非0數字的位置,
遍歷整個陣列/串列,當元素非0時,則將其寫入index的位置,
並遞增index,其程式碼如下所示。

Java:

class Solution {
    public void moveZeroes(int[] nums) {
        int index = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nums[index++] = nums[i];
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }
    }
}

Python:

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        index = 0
        for i in range(len(nums)):
            if nums[i]:
                nums[index] = nums[i]
                index += 1
        for j in range(index, len(nums)):
            nums[j] = 0

面試實際可能會遇到的問題:
「時間/空間複雜度?」
(O(N), O(1),因為最多只須掃過陣列兩次即可)

「如果不要求順序保持相同的話呢?」
(使用two pointer的方式,i由頭至尾,j由尾至頭,
分別找到0和非0的元素進行交換,直到彼此交會即可。
時間/空間複雜度相同但可預期因只須掃過一次陣列,有機會較快)

「如果不要求要in-place呢?」
(以python為例:
res=[x for x in nums if x != 0]
res += (len(nums)- len(res)) * [0]
(後面再接上對應個數的0即可)
(時間/空間複雜度O(N),O(N))

所以,有些題目簡單歸簡單,看到的時候,還是請留心限制條件,
它有可能跟你熟悉的題目有些出入!有時候一旦限制條件不同,
可以用的手段和時間/空間複雜度可能就會完全不同了!

從LeetCode學演算法,我們下次見囉,掰~

下篇預告:
0096. Unique Binary Search Trees (Medium)


上一篇
[Day 25] 從LeetCode學演算法 - 0063. Unique Paths II (Medium)
下一篇
[Day 27] 從LeetCode學演算法 - 0096. Unique Binary Search Trees (Medium)
系列文
從LeetCode學演算法30

尚未有邦友留言

立即登入留言