iT邦幫忙

0

Leetcode/AlgoExpert 解題筆記 – Array 篇 (1)

嗨大家好,這系列的文章主要是想紀錄我在寫 Leetcode / AlgoExpert 的題目時的一些所思所想,跟大家分享之餘也做個筆記,方便日後需要的時候可以回顧。

因為是第一篇,所以先牛刀小試一下,這則文章裡的題目都是跟 Array 有關的題目,難度基本上都是 Leetcode easy 的 level。另外,在這系列的文章裡面將會使用 Java 作為實作的程式語言。

那就廢話不多說,讓我們開始吧!

Squares of a Sorted Array

題目

給定一個 int[] nums,裡面元素為 non-decreasing 排列,需回傳一個 array 以 non-decreasing 排列平方後的元素。

Example

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Brute Force

最暴力的解法就是,我們先迭代 nums 得出平方後的 array(以範例來說就是 [16, 1, 0, 9, 100],然後再 sort 這個 array。

但是這樣 time compleity 會取決你用的 sorting method,可見下表。

但不管使用哪種 sorting algorithm,time complexity 都沒有比 https://chart.googleapis.com/chart?cht=tx&chl=O(N) 好。

Improvement

要有比較好的 performance,我們必須要利用題目給的線索,那就是 non-decreasing。input 跟 output 都要是 non-decreasing order,但我們不能直接把 output 照 input 的順序排,因為有的負數平方過後會比正數的平方來得大。

但是我們可以注意到一件事,正數與正數之間或是負數與負數之間,在平方過後的順序是會一致的。如果把正數跟負數拆開,兩邊都按照順序排列,每次都從兩者中挑出比較大的那個放入目標,然後繼續看下一個,如此兩兩一組去看,最後就可以排出來了。

這麼說有點模糊,想像成兩組人,兩組都按身高從高排到低。一開始看兩邊最高的人誰高,假設第一排的人比較高,就把他叫去第三排當第一個,然後再接著比第一排第二高的人跟第二排最高的人誰高,高的就叫他離開原本那排去第三排接著排隊,以此類推直到所有人都排到第三排為止。

所以其實我們要做的就是讓正數自己一排,負數也一排,要怎麼做?我們就讓負數從 array 的頭開始,然後讓正數從 array 的尾巴開始,兩兩比較他們的「絕對值」,誰比較大就把它平方,然後塞到要 return 的 array 的最尾巴。接著,如果是頭的數被移掉,頭就往右邊一格;反之,如果是尾巴被移掉,就往左邊一格。

你可能想,如果頭在往右移的過程中,指到的數字變成正的;或是尾巴在往左移的過程中,指到的數字變成負的怎麼辦?其實不影響,因為頭如果變成指到正數,代表剩下的都是正數,所以尾巴指的數字接下來一定都比頭指到的大,也就是說頭接下來都不會移動了,反之亦然。我們只要重複這個操作到頭跟尾巴指到同一個數字即可。

而整個過程我們只有迭代 input array 一次,而且每次的操作都是 constant time,所以總 time complexity 為 https://chart.googleapis.com/chart?cht=tx&chl=O(N)

Implementation


class Solution {
    public int[] sortedSquares(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int inserting = nums.length-1;
        int[] sorted = new int[nums.length];
        
        while (start != end) {
            int startValue = nums[start] * nums[start];
            int endValue = nums[end] * nums[end];
            
            if (startValue > endValue) {
                sorted[inserting] = startValue;
                start += 1;
            } else {
                sorted[inserting] = endValue;
                end -= 1;
            }
            inserting -= 1;
        }
        
        sorted[inserting] = nums[start] * nums[start];
        
        return sorted;
    }
}

Duplicate Zeros

題目

給定一個固定長度 array int[] nums,將 array 裡面出現的每個 0 複製一次,並把所有元素往右移。如果超過 array 長度,則丟棄那些溢出的元素。

不可以另外建立新的 array 回傳,必須修改原有的 array(in-place operation)。

Example

Input: [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]

觀察

這題因為不能額外建立新的 array 去儲存,所以我們只能去修改原本的 array。可是麻煩的是我們必須要 duplicate 0,這會導致接在 0 後面的元素被蓋掉。

要解決這問題,我們就要用變數去記住稍後會被蓋掉的元素,可是當 0 很多個或是連續出現好幾個的時候,我們就要提前去記住接下來很多個會被蓋掉的元素,邏輯會很複雜,也沒辦法預預測你必須要保留多少個會被蓋掉的變數,如此就要用 array-like 的資料結構去記,那就失去不能使用新的 array 這個限制的意義了。

Brute Force

我們可以觀察到,一定是後面的元素會被前面的擠掉,不會是前面被後面擠掉,因為整個 array 是往右 shift 的。

我們也可以發現,只要有一個 0 出現,那就代表從 array 的尾巴會有一個元素被擠掉。所以,我們就從 array 的頭開始出發,每遇到一個 0,我們就把從這個 0 以後的所有元素往右一格,直到最後一個元素就行。

Implementation

class Solution() {
    public void duplicateZeros(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                for (int j = arr.length-1; j > i; j--) {
                    arr[j] = arr[j-1];    // 把每個元素都往右移
                }
                i++;    // 跳過被 duplicate 的 0,從原本 array 下一個元素繼續
            }
        }
    }
}

但是這個解法的 time complexity(in worst case) 會是 https://chart.googleapis.com/chart?cht=tx&chl=O(N%5E2),可以看到我們的 for loop 包了兩層,這個解法的迭代過程有點類似 bubble sort。

較好的解法

我們可以先透過掃描一次 array 去知道,從第幾個元素開始,後面的元素都會因為溢出而不會被寫到 array 裡。然後,從這個位置開始往 array 的頭回推,遇到 0 的話就填入兩個 0,不是 0 的話就填入該元素就好。

下面是示意圖

因為我們已經算過到第幾個元素會是儲存的界限,所以你會看到,留下來的 array 中有幾個 0,就應該是這個留下來的 array 的長度跟初始 array 長度的差。(e.g. [1,0,2,3,0,4] 長度為 6,有兩個 0,6+2 剛好會是初始 array [1,0,2,3,0,4,5,0] 的長度。

我們就從 4 開始往回,從初始 array 的最後一個往回塞,遇到 0 就連續填兩個 0;遇到其他的就填入當下遇到的數字。

Implementation

class Solution() {
    public void duplicateZeros(int[] arr) {
        int lastValidIndex = 0;    // 紀錄最後不會溢出的元素 index
        int count = 0;    // 紀錄是否已經超出 array 長度
        
        while (true) {
            if (arr[lastValidIndex] == 0) {
                count += 2;    // 如果是 0,要佔兩格
            } else {
                count += 1;
            }
            // 若前面元素佔掉的空間已經超過 array 長度,就跳出,否則繼續往下算
            if (count < arr.length) {  
                lastValidIndex += 1;
            } else {
                break;
            }
        }
        
        // 如果 count 超出長度,代表最後一個是 0,而且這個 0 所產生的 duplicate 溢出,不會重複。
        // 把最後一個填入 0,而且把有效的 index 往左一格
        int insertingIndex = arr.length-1;
        if (count > arr.length) {
            arr[arr.length-1] = 0;
            insertingIndex -= 1;
            lastValidIndex -= 1;
        }
        
        
        for (int i = lastValidIndex; i >= 0; i--) {
            if (arr[i] == 0) { // 0 -> 填入兩個 0,下一個填入的 index 往左兩格
                arr[insertingIndex] = 0;
                arr[insertingIndex-1] = 0;
                insertingIndex -= 2;
            } else { // 非 0 -> 填入該元素,下一個填入的 index 往左一格
                arr[insertingIndex] = arr[i];
                insertingIndex -= 1;
            }
        }
    }
}

Merge Sorted Array

題目

給定 int[] nums1int[] nums2,其中 nums1 含有 m 個元素,nums2 含有 n 個元素,兩者皆為 sorted (in asecnding order)。

將兩者合併成一個 sorted array (in ascending order),必須將 nums2 合併到 nums1 中,不可建立新的 array,extra memory space 只能為 https://chart.googleapis.com/chart?cht=tx&chl=O(1)

另外,nums1 的長度為 m+n,但只有前 m 個元素為有值的元素,後面的 n 個為 0,不代表數字 0,而是空值的意思。

Examples

Input: 
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]

Output: [1,2,2,3,5,6]

Brute Force

每次從 nums2 取出一個元素(稱 b),從 nums1 的頭開始迭代,找到 b 對應插入的位置後,將後面的 nums1 元素全部往右一格。

接著,繼續迭代下一個 nums2 元素,從插入上一個 nums2 元素的位置繼續往下比對,找到要插入的位置後,一樣把該位置後面的所有 nums1 元素往右移一格。如此反覆操作直到 nums2 元素全部迭代完。

trick

每次插入 nums2 元素時,可以檢查是不是插在當下最後面了,如果是的話,就代表這個 nums2 的元素已經比所有 nums1 元素來得大。因此接下來就直接把剩下的 nums2 元素從這個位置往後依序排放即可。

不過這個解法並不好,有以下兩個原因

  1. 我們要迭代每個 nums2 的元素,在處理每一個 nums2 的元素,又要先迭代 nums1 的所有元素,找到插入位置後,又要把此位置後的元素全部往右移,因此又要再迭代一次。這樣三層包下來,time complexity會是 https://chart.googleapis.com/chart?cht=tx&chl=O(N*(M%2BN)%5E2)
  2. 邏輯不好寫,要設置往右移的起點跟終點,沒寫好的話可能會遇到 index out of bounds 的問題。

較好的解法

我們要怎麼 improve 上面的解法呢?答案就是我們從 後面 開始比較,不要從前面。

因為 nums1 前 m 個元素跟 nums2 前 n 個元素都是從小排到大,而且 nums1 後 n 個 entry 都是空的,所以我們就從 nums1 的第 m 個還有 nums2 的第 n 個開始比大小,誰比較大誰就去從 nums1 的最後面插入 nums1。接著,拿下一個元素往下,如此兩兩比較到 nums1nums2 的第一個元素已經被放到後面為止。

Implementation

class Solution() {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1; // nums1 從第 m 個開始比
        int index2 = n - 1; // nums2 從第 n 個開始比
        int inserting = m + n - 1; // 從 nums1 的最後面開始 insert
        
        while (true) {
            if (index1 < 0) { // 如果 nums1 的 m 個全部被取完
                // 剩下的都是 nums2,把 nums2 剩下的放到 nums1 最前面
                for (int i = index2; i >= 0; i--) {
                    nums1[i] = nums2[i];
                }
                break;
            }
            
            if (index2 < 0) { // 如果 nums2 的 n 個全部被取完
                // 剩下的都是 nums1,不用動
                break;
            }
            
            // 兩者皆尚未取完
            int val1 = nums1[index1];
            int val2 = nums2[index2];
            if (val1 > val2) { // nums1 的比較大
                nums1[inserting] = val1;
                index1 -= 1; // 指到 nums1 下一個元素
            } else { // nums2 的比較大
                nums1[inserting] = val2;
                index2 -= 1; // 指到 nums2 下一個元素
            }
            inserting -= 1; // 插入的位置往左移一格
        }
    }
}

Remove Element

題目

給定一個 int[] nums 和一個 int val,計算nums 中不等於 val 的個數有幾個(假設為 N),並且修改 nums,讓其前 N 個元素是那些不等於 val 的元素(順序不重要)。

此題必須要修改原有的 nums,不可額外建立新的 array 或其他 data structures,extra space memory 為 https://chart.googleapis.com/chart?cht=tx&chl=O(1)

Examples

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2]

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5,  nums = [0,1,4,0,3] (不用考慮這五個元素排列順序)

較差的解法

假設 valnums 裡面有 m 個,array size 為 n,那麼我們要做的就是把其他元素放在 array 的前 n-m 個。

一個較差的解法就是一樣分別從頭尾兩端去檢查,因為我們要把等於 val 的元素往後送,所以只要檢查到前面的元素是 val 而且後面的元素是 val 時,我們就把兩者互換,並且兩個指標都往中間繼續靠攏。

然後,如果上面條件不成立,那就還要看兩個條件。如果前面指標指到的元素是 val,那就不能繼續往後跳,要等後面的指標指到不是 val 的元素時要互換,如果前面指到的元素不是 val,那就繼續往後跳。 而後面的指標則相反,指到不是 val 的元素時要停下來,否則繼續往前。

Implementation

class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums.length == 0) return 0;
        
        int start = 0;
        int end = nums.length - 1;
        
        while (start < end) {
            if (nums[start] == val && nums[end] != val) {
                nums[start] = nums[end];
                nums[end] = val;
                end -= 1;
            }
            if (nums[end] == val) {
                end -= 1;
            }
            if (nums[start] != val && start < end) {
                start += 1;
            }
        }
        
       if (nums[end] == val) {
           return end;
       } else {
           return end+1;
       }
    }
}

但是可以看到,這個解法寫起來有點麻煩,而且需要去考慮 startend 的關係,像是 nums 裡面只有一個或零個元素時,沒有處理好就可能會出現 index out of bound。

Read/Write Pointer (Fast-Slow Pointer)

我們可以使用一樣使用兩個指標來解這題,只不過這次我們讓兩者都從 array 的最前面開始,我們取名為 readwrite。所謂 Read/Write 是指一個指標用於讀取、一個用於寫入,讀取的會比寫入跑得快,當條件符合的時候,會把讀取指標指到的元素 copy 給寫入指標的元素。

如果 read 指到的元素不是 val,那就把值 assign 給 read 所在的那格,並且兩者都往後一格;如果 read 指到的元素是 val,那就不動,繼續往下。

這個解法乍聽下來不知道為什麼可以 work,但其實很簡單,我們讓 readnums 第一格往後,就是會迭代每一個元素。而當它指到的元素不是 val 時,就會把這個值往前塞,總共會塞幾次?答案是 n-m 次,因為總共有 n 個元素,其中有 m 個等於 val,所以不等於 val 的就是 n-m。而 write 一開始也是指到 nums 第一格(index 為 0),而它只有在 read 指到的元素不是 val 時才會將指到的該格往下,總共會進行 n-m 次,所以會將 numsn-m 格換成不是 val 的元素,而且不會有重複的問題,因為 read 只會指到每個元素一次。

Implementation

class Solution {
    public int removeElement(int[] nums, int val) {
        int pointer1, pointer2;
        pointer1 = pointer2 = 0;
        
        while (pointer2 < nums.length) {
            if (nums[pointer2] != val) {
                nums[pointer1] = nums[pointer2];
                pointer1++;
                pointer2++;
            } else {
                pointer2++;
            }
        }
        
        return pointer1;
    }
}

這個解法不僅 performance 來得好一點,更重要的是大大地提升了閱讀性。

:::info
此題與 Remove Duplicates from Sorted Array 非常相似,可以互相參考。
:::

Replace Elements with Greatest Element on Right Side

題目

給定一 int[] arr,將每個元素替換成該元素右邊所有元素中最大值,最後一個元素則替換成 -1。

不可建立新的 array,extra space complexity 為 https://chart.googleapis.com/chart?cht=tx&chl=O(1)

Examples

Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]

Brute Force

要將每個元素替換成右邊最大的元素,那就迭代每個元素,則該元素被迭代的時候,再用一層 for loop 去迭代該元素「右邊的所有元素」(0 -> 1,2,3,4,5 / 1 -> 2,3,4,5 ...)。

在迭代右邊所有元素的過程中,記下出現的最大值,然後把該元素替換成最大值,如此重複到 array 倒數第二個元素就行,因為最後一個沒有右邊的元素,直接替換成 -1。

雖然簡單明瞭,但是可以想見,這個解法的 time complexity 不會好,因為它疊了兩層的 for loop,time complexity 會是 https://chart.googleapis.com/chart?cht=tx&chl=O(N%5E2),是一個 brute force 的解法。

Implementation

class Solution {
    public int[] replaceElements(int[] arr) {
        int max;
        
        for (int i = 0; i < arr.length-1; i++) {
            max = arr[i+1];
            for (int j = i+2; j < arr.length; j++) {
                if (arr[j] > max) {
                    max = arr[j];
                }
            }
            arr[i] = max;
        }
        
        arr[arr.length-1] = -1;
        
        return arr;
    }
}

較好的解法

有沒有辦法只迭代一次 array 我們就可以完成這項任務呢?是可以的!我們只要從 array 的末端開始就辦得到。

可以看到,從前面開始的話我們會遇到一個問題,假設我們第一次迭代整個 array 找到最大值,但我們不能把這個最大值應用到所有人身上,因為隨著往右走的過程中,會越過這個成為最大值的元素,接下來這些元素其右邊所有元素的最大值就不是整個 array 的最大值了,所以我們又要重新去找。

但是如果從末端開始就沒有這個問題,我們再從末端找回尾端的過程中一直紀錄最大值,到了該元素時,就直接把該元素替換成目前的最大值就行了。不過我們要注意,這個元素是不是大於最大值,如果是的話,就要把最大值替換成這個元素,最大值替換成元素,元素替換成最大值,不是會互相覆蓋嗎?沒錯,要做這種 swapping 的話就必須要有一個額外的變數來暫存其中ㄧ者。

Implementation

class Solution {
    public int[] replaceElements(int[] arr) {
        // initialize maximum to the last entry
        int max = arr[arr.length-1];
        
        // replace last entry with -1
        arr[arr.length-1] = -1;
        
        int temp;
        // iterate the array from the end
        for (int i = arr.length-2; i > -1; i--) {
            // store current iterating entry to temp
            temp = arr[i];
            
            // assign maximum to the current iterating entry
            arr[i] = max;
            
            // compare temp with maximum to decide new maximum
            if (temp > max) {
                max = temp;
            }
        }
           
        return arr;
    }
}

只迭代了一次 array,time complexity 瞬間從 https://chart.googleapis.com/chart?cht=tx&chl=O(N%5E2) 掉到 https://chart.googleapis.com/chart?cht=tx&chl=O(N),Leetcode 的 runtime 則從 143ms 直接掉到 1ms。

Sort Array By Parity

題目

給定一個 int[] A,裡面的每個元素都為 non-negative integers,回傳一個 array,裡面所有偶數 elements 必須排列在所有奇數 elements 前面。(不用考慮偶數與偶數間、奇數與奇數間的順序)

Examples

Input: [3,1,2,4]
Output: [2,4,1,3] / [2,4,3,1]  [4,2,1,3] / [4,2,3,1]

O(N) for both Time & Space

因為這個題目是要求回傳一個 array,沒有規定不能用新的 array,所以是可以建立新的 array。

我們可以建立一個新的 array int[] B,長度與 A 相同。接著我們可以 loop through A,遇到奇數的時候放到 B 的尾端,並且把尾端往左一格;遇到偶數的時候放到 B 的頭端,並且把頭端往右一格,直到迭代完 A 的所有元素。

雖然這個解法的 time complexity 為 https://chart.googleapis.com/chart?cht=tx&chl=O(N),但是 space complexity 也為https://chart.googleapis.com/chart?cht=tx&chl=O(N)

較好的解法

前面講了這麼多題現在應該也猜到,較好的解法就是要用 in-place operation,將 time complexity 維持在 https://chart.googleapis.com/chart?cht=tx&chl=O(N) 的同時也將 space complexity 降為 https://chart.googleapis.com/chart?cht=tx&chl=O(1)

而應該也不難猜到,我們要使用的技巧就是前面遇到爛的 two-pointer technique

而這題我們將兩個 pointer 分別從 array 的頭與尾開始,我們的目標是要將偶數全部放到前面、奇數全部放到後面。所以也就是說,從前面開始的 pointer 遇到奇數時,應該要把它往後丟、從後面開始的 pointer 遇到偶數時,應該要把它往前丟。

所以當這兩個條件都成立的時候,我們就把兩者位置互換,讓奇數去後面、後數去前面。那如果只有一個條件成立呢?那就是讓條件不成立的那個 pointer 繼續往中間移動,直到兩個條件成立。什麼時候會停?當兩個 pointer 交會的時候就停下來。

Implementation

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int start = 0; // 從前面開始的 pointer
        int end = A.length-1; // 從後面開始的 pointer
        
        int temp; // 用於 swapping
        while (start < end) { // 當兩者還沒交會,繼續往中間找
            // 兩個條件都成立,互換,並且都往中間移動一格
            if (A[end] % 2 == 0 && A[start] % 2 == 1) {
                temp = A[end];
                A[end] = A[start];
                A[start] = temp;
                start += 1;
                end -= 1;
            } else {
                // 後面的不是偶數,往下(中間)一格找
                if (A[end] % 2 == 1) {
                    end -= 1;
                }
                // 前面的不是奇數,往下(中間)一格找
                if (A[start] % 2 == 0) {
                    start += 1;
                }    
            }
        }
        
        return A;
    }
}

尚未有邦友留言

立即登入留言