用户投稿嗨大家好，这系列的文章主要是想纪录我在写 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 都没有比 好。
Improvement
要有比较好的 performance，我们必须要利用题目给的线索，那就是 non-decreasing。input 跟 output 都要是 non-decreasing order，但我们不能直接把 output 照 input 的顺序排，因为有的负数平方过后会比正数的平方来得大。
但是我们可以注意到一件事，正数与正数之间或是负数与负数之间，在平方过后的顺序是会一致的。如果把正数跟负数拆开，两边都按照顺序排列，每次都从两者中挑出比较大的那个放入目标，然后继续看下一个，如此两两一组去看，最后就可以排出来了。
这么说有点模糊，想像成两组人，两组都按身高从高排到低。一开始看两边最高的人谁高，假设第一排的人比较高，就把他叫去第三排当第一个，然后再接着比第一排第二高的人跟第二排最高的人谁高，高的就叫他离开原本那排去第三排接着排队，以此类推直到所有人都排到第三排为止。
所以其实我们要做的就是让正数自己一排，负数也一排，要怎么做？我们就让负数从 array 的头开始，然后让正数从 array 的尾巴开始，两两比较他们的「绝对值」，谁比较大就把它平方，然后塞到要 return 的 array 的最尾巴。接着，如果是头的数被移掉，头就往右边一格；反之，如果是尾巴被移掉，就往左边一格。
你可能想，如果头在往右移的过程中，指到的数字变成正的；或是尾巴在往左移的过程中，指到的数字变成负的怎么办？其实不影响，因为头如果变成指到正数，代表剩下的都是正数，所以尾巴指的数字接下来一定都比头指到的大，也就是说头接下来都不会移动了，反之亦然。我们只要重複这个操作到头跟尾巴指到同一个数字即可。
而整个过程我们只有迭代 input array 一次，而且每次的操作都是 constant time，所以总 time complexity 为 。
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) 会是 ，可以看到我们的 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[] 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，而是空值的意思。
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 元素从这个位置往后依序排放即可。
不过这个解法并不好，有以下两个原因
我们要迭代每个nums2 的元素，在处理每一个 nums2 的元素，又要先迭代 nums1 的所有元素，找到插入位置后，又要把此位置后的元素全部往右移，因此又要再迭代一次。这样三层包下来，time complexity会是 较好的解法
我们要怎么 improve 上面的解法呢？答案就是我们从 后面 开始比较，不要从前面。
因为 nums1 前 m 个元素跟 nums2 前 n 个元素都是从小排到大，而且 nums1 后 n 个 entry 都是空的，所以我们就从 nums1 的第 m 个还有 nums2 的第 n 个开始比大小，谁比较大谁就去从 nums1 的最后面插入 nums1。接着，拿下一个元素往下，如此两两比较到 nums1 或 nums2 的第一个元素已经被放到后面为止。
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 为 。
Examples
Input: nums = [3,2,2,3], val = 3Output: 2, nums = [2,2]Input: nums = [0,1,2,2,3,0,4,2], val = 2Output: 5, nums = [0,1,4,0,3] (不用考虑这五个元素排列顺序)较差的解法
假设 val 在 nums 里面有 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; } }}但是可以看到，这个解法写起来有点麻烦，而且需要去考虑 start 跟 end 的关係，像是 nums 里面只有一个或零个元素时，没有处理好就可能会出现 index out of bound。
Read/Write Pointer (Fast-Slow Pointer)
我们可以使用一样使用两个指标来解这题，只不过这次我们让两者都从 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 只会指到每个元素一次。
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 为 。
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 会是 ，是一个 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 瞬间从 掉到
，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 为 ，但是 space complexity 也为
。
较好的解法
前面讲了这么多题现在应该也猜到，较好的解法就是要用 in-place operation，将 time complexity 维持在 的同时也将 space complexity 降为
。
而应该也不难猜到，我们要使用的技巧就是前面遇到烂的 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; }}
微信扫一扫打赏
支付宝扫一扫打赏
