嗨大家好，這系列的文章主要是想紀錄我在寫 Leetcode / AlgoExpert 的題目時的一些所思所想，跟大家分享之餘也做個筆記，方便日後需要的時候可以回顧。
因為是第一篇，所以先牛刀小試一下，這則文章裡的題目都是跟 Array 有關的題目，難度基本上都是 Leetcode easy 的 level。另外，在這系列的文章裡面將會使用 Java 作為實作的程式語言。
那就廢話不多說，讓我們開始吧！
給定一個 int[] nums，裡面元素為 non-decreasing 排列，需回傳一個 array 以 non-decreasing 排列平方後的元素。
ianyshuang
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
最暴力的解法就是，我們先迭代 nums 得出平方後的 array（以範例來說就是 [16, 1, 0, 9, 100]，然後再 sort 這個 array。
但是這樣 time compleity 會取決你用的 sorting method，可見下表。
但不管使用哪種 sorting algorithm，time complexity 都沒有比 好。
要有比較好的 performance，我們必須要利用題目給的線索，那就是 non-decreasing。input 跟 output 都要是 non-decreasing order，但我們不能直接把 output 照 input 的順序排，因為有的負數平方過後會比正數的平方來得大。
但是我們可以注意到一件事，正數與正數之間或是負數與負數之間，在平方過後的順序是會一致的。如果把正數跟負數拆開，兩邊都按照順序排列，每次都從兩者中挑出比較大的那個放入目標，然後繼續看下一個，如此兩兩一組去看，最後就可以排出來了。
這麼說有點模糊，想像成兩組人，兩組都按身高從高排到低。一開始看兩邊最高的人誰高，假設第一排的人比較高，就把他叫去第三排當第一個，然後再接著比第一排第二高的人跟第二排最高的人誰高，高的就叫他離開原本那排去第三排接著排隊，以此類推直到所有人都排到第三排為止。
所以其實我們要做的就是讓正數自己一排，負數也一排，要怎麼做？我們就讓負數從 array 的頭開始，然後讓正數從 array 的尾巴開始，兩兩比較他們的「絕對值」，誰比較大就把它平方，然後塞到要 return 的 array 的最尾巴。接著，如果是頭的數被移掉，頭就往右邊一格；反之，如果是尾巴被移掉，就往左邊一格。
你可能想，如果頭在往右移的過程中，指到的數字變成正的；或是尾巴在往左移的過程中，指到的數字變成負的怎麼辦？其實不影響，因為頭如果變成指到正數，代表剩下的都是正數，所以尾巴指的數字接下來一定都比頭指到的大，也就是說頭接下來都不會移動了，反之亦然。我們只要重複這個操作到頭跟尾巴指到同一個數字即可。
而整個過程我們只有迭代 input array 一次，而且每次的操作都是 constant time，所以總 time complexity 為 。
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;
}
}
給定一個固定長度 array int[] nums，將 array 裡面出現的每個 0 複製一次，並把所有元素往右移。如果超過 array 長度，則丟棄那些溢出的元素。
不可以另外建立新的 array 回傳，必須修改原有的 array（in-place operation）。
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 這個限制的意義了。
我們可以觀察到，一定是後面的元素會被前面的擠掉，不會是前面被後面擠掉，因為整個 array 是往右 shift 的。
我們也可以發現，只要有一個 0 出現，那就代表從 array 的尾巴會有一個元素被擠掉。所以，我們就從 array 的頭開始出發，每遇到一個 0，我們就把從這個 0 以後的所有元素往右一格，直到最後一個元素就行。
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) 會是 ，可以看到我們的 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；遇到其他的就填入當下遇到的數字。
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;
}
}
}
}
給定 int[] nums1、int[] nums2，其中 nums1 含有 m 個元素，nums2 含有 n 個元素，兩者皆為 sorted (in asecnding order)。
將兩者合併成一個 sorted array (in ascending order)，必須將 nums2 合併到 nums1 中，不可建立新的 array，extra memory space 只能為 。
另外，nums1 的長度為 m+n，但只有前 m 個元素為有值的元素，後面的 n 個為 0，不代表數字 0，而是空值的意思。
Input:
nums1 = [1,2,3,0,0,0]
nums2 = [2,5,6]
Output: [1,2,2,3,5,6]
每次從 nums2 取出一個元素（稱 b），從 nums1 的頭開始迭代，找到 b 對應插入的位置後，將後面的 nums1 元素全部往右一格。
接著，繼續迭代下一個 nums2 元素，從插入上一個 nums2 元素的位置繼續往下比對，找到要插入的位置後，一樣把該位置後面的所有 nums1 元素往右移一格。如此反覆操作直到 nums2 元素全部迭代完。
每次插入 nums2 元素時，可以檢查是不是插在當下最後面了，如果是的話，就代表這個 nums2 的元素已經比所有 nums1 元素來得大。因此接下來就直接把剩下的 nums2 元素從這個位置往後依序排放即可。
不過這個解法並不好，有以下兩個原因
nums2 的元素，在處理每一個 nums2 的元素，又要先迭代 nums1 的所有元素，找到插入位置後，又要把此位置後的元素全部往右移，因此又要再迭代一次。這樣三層包下來，time complexity會是 我們要怎麼 improve 上面的解法呢？答案就是我們從 後面 開始比較，不要從前面。
因為 nums1 前 m 個元素跟 nums2 前 n 個元素都是從小排到大，而且 nums1 後 n 個 entry 都是空的，所以我們就從 nums1 的第 m 個還有 nums2 的第 n 個開始比大小，誰比較大誰就去從 nums1 的最後面插入 nums1。接著，拿下一個元素往下，如此兩兩比較到 nums1 或 nums2 的第一個元素已經被放到後面為止。
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; // 插入的位置往左移一格
}
}
}
給定一個 int[] nums 和一個 int val，計算nums 中不等於 val 的個數有幾個（假設為 N），並且修改 nums，讓其前 N 個元素是那些不等於 val 的元素（順序不重要）。
此題必須要修改原有的 nums，不可額外建立新的 array 或其他 data structures，extra space memory 為 。
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] (不用考慮這五個元素排列順序)
假設 val 在 nums 裡面有 m 個，array size 為 n，那麼我們要做的就是把其他元素放在 array 的前 n-m 個。
一個較差的解法就是一樣分別從頭尾兩端去檢查，因為我們要把等於 val 的元素往後送，所以只要檢查到前面的元素是 val 而且後面的元素是 val 時，我們就把兩者互換，並且兩個指標都往中間繼續靠攏。
然後，如果上面條件不成立，那就還要看兩個條件。如果前面指標指到的元素是 val，那就不能繼續往後跳，要等後面的指標指到不是 val 的元素時要互換，如果前面指到的元素不是 val，那就繼續往後跳。 而後面的指標則相反，指到不是 val 的元素時要停下來，否則繼續往前。
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;
}
}
}
但是可以看到，這個解法寫起來有點麻煩，而且需要去考慮 start 跟 end 的關係，像是 nums 裡面只有一個或零個元素時，沒有處理好就可能會出現 index out of bound。
我們可以使用一樣使用兩個指標來解這題，只不過這次我們讓兩者都從 array 的最前面開始，我們取名為 read、write。所謂 Read/Write 是指一個指標用於讀取、一個用於寫入，讀取的會比寫入跑得快，當條件符合的時候，會把讀取指標指到的元素 copy 給寫入指標的元素。
如果 read 指到的元素不是 val，那就把值 assign 給 read 所在的那格，並且兩者都往後一格；如果 read 指到的元素是 val，那就不動，繼續往下。
這個解法乍聽下來不知道為什麼可以 work，但其實很簡單，我們讓 read 從 nums 第一格往後，就是會迭代每一個元素。而當它指到的元素不是 val 時，就會把這個值往前塞，總共會塞幾次？答案是 n-m 次，因為總共有 n 個元素，其中有 m 個等於 val，所以不等於 val 的就是 n-m。而 write 一開始也是指到 nums 第一格（index 為 0），而它只有在 read 指到的元素不是 val 時才會將指到的該格往下，總共會進行 n-m 次，所以會將 nums 前 n-m 格換成不是 val 的元素，而且不會有重複的問題，因為 read 只會指到每個元素一次。
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 非常相似，可以互相參考。
:::
給定一 int[] arr，將每個元素替換成該元素右邊所有元素中最大值，最後一個元素則替換成 -1。
不可建立新的 array，extra space complexity 為 。
Input: arr = [17,18,5,4,6,1]
Output: [18,6,6,6,1,-1]
要將每個元素替換成右邊最大的元素，那就迭代每個元素，則該元素被迭代的時候，再用一層 for loop 去迭代該元素「右邊的所有元素」（0 -> 1,2,3,4,5 / 1 -> 2,3,4,5 ...）。
在迭代右邊所有元素的過程中，記下出現的最大值，然後把該元素替換成最大值，如此重複到 array 倒數第二個元素就行，因為最後一個沒有右邊的元素，直接替換成 -1。
雖然簡單明瞭，但是可以想見，這個解法的 time complexity 不會好，因為它疊了兩層的 for loop，time complexity 會是 ，是一個 brute force 的解法。
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 的話就必須要有一個額外的變數來暫存其中ㄧ者。
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 瞬間從 掉到
，Leetcode 的 runtime 則從 143ms 直接掉到 1ms。
給定一個 int[] A，裡面的每個元素都為 non-negative integers，回傳一個 array，裡面所有偶數 elements 必須排列在所有奇數 elements 前面。（不用考慮偶數與偶數間、奇數與奇數間的順序）
Input: [3,1,2,4]
Output: [2,4,1,3] / [2,4,3,1] [4,2,1,3] / [4,2,3,1]
因為這個題目是要求回傳一個 array，沒有規定不能用新的 array，所以是可以建立新的 array。
我們可以建立一個新的 array int[] B，長度與 A 相同。接著我們可以 loop through A，遇到奇數的時候放到 B 的尾端，並且把尾端往左一格；遇到偶數的時候放到 B 的頭端，並且把頭端往右一格，直到迭代完 A 的所有元素。
雖然這個解法的 time complexity 為 ，但是 space complexity 也為
。
前面講了這麼多題現在應該也猜到，較好的解法就是要用 in-place operation，將 time complexity 維持在 的同時也將 space complexity 降為
。
而應該也不難猜到，我們要使用的技巧就是前面遇到爛的 two-pointer technique。
而這題我們將兩個 pointer 分別從 array 的頭與尾開始，我們的目標是要將偶數全部放到前面、奇數全部放到後面。所以也就是說，從前面開始的 pointer 遇到奇數時，應該要把它往後丟、從後面開始的 pointer 遇到偶數時，應該要把它往前丟。
所以當這兩個條件都成立的時候，我們就把兩者位置互換，讓奇數去後面、後數去前面。那如果只有一個條件成立呢？那就是讓條件不成立的那個 pointer 繼續往中間移動，直到兩個條件成立。什麼時候會停？當兩個 pointer 交會的時候就停下來。
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;
}
}
iThome鐵人賽
看影片追技術