這篇會講解Array Operation 有關新增和搜尋的題目，因為刪除操作的題目跟原地操作的題目重疊，所以在下一篇才會講解。

1089. Duplicate Zeros

題目

Input 是一個整數陣列，陣列長度介於1至10^4之間，陣列元素大小介於0至9之間。
它沒有回傳值，是指定要把原陣列中的0從左至右的複製一次，每複製一次就把剩下的元素往後移動。

Example 1:

Input: arr = [1,0,2,3,0,4,5,0]
Output: [1,0,0,2,3,0,0,4]
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: arr = [1,2,3]
Output: [1,2,3]
Explanation: After calling your function, the input array is modified to: [1,2,3]

解法(Java)

這題目我翻譯起來感覺怪怪的，但我想到的原地操作方法會花費很多時間，倒不如直接另外建一個陣列暫存結果，跑完一圈得到結果之後再複製回輸入的陣列。

Runtime: 1 ms
Memory Usage: 43.4 MB

class Solution {
    public void duplicateZeros(int[] arr) {
        int len = arr.length;
        int[] temp = new int[len];
        for (int i = 0, j = 0; i < len && j < len; i++, j++) {
            temp[i] = arr[j];
            if (arr[j] == 0 && i + 1 < len) {
                temp[++i] = 0;
            }
        }
        
        for (int i = 0; i < len; i++) {
            arr[i] = temp[i];
        }
    }
}

88. Merge Sorted Array

題目

Input 會給兩個陣列(nums1 和nums2)，它們都是經過排序的正整數陣列，還會再給兩個整數(m 和n)，它們代表著兩個陣列要取的數量。
Output 根據輸入的變數，nums1 取出前m 個元素，nums2 取出前n 個元素，合併在nums1 之中，並且要排序。

另外，nums1 的陣列長度是m+n，nums2 的陣列長度是n，m 和n 的大小介於0至200之間，m+n的大小介於1至200之間，nums1 和nums2 兩陣列內元素大小介於-10^9至10^9之間。

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

解法(Java)

題目內容有點長，而且還有個Follow up，它想要我們的解法是O(m+n)。
它的解法是要倒過來走，從nums1 的尾端開始新增元素，nums1 只會取前m個值，nums2 也只會取前n個值，因此就從第第m-1個元素和第n-1個元素開始比大小，比較大的就放進尾端，不斷往前新增。

Runtime: 0 ms
Memory Usage: 40.9 MB

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last1 = m - 1;
        int last2 = n - 1;
        
        while (last2 >= 0) {
            if (last1 >= 0 && nums1[last1] > nums2[last2]) {
                nums1[last1 + last2 + 1] = nums1[last1];
                last1--;
            } else {
                nums1[last1 + last2 + 1] = nums2[last2];
                last2--;
            }
        }
    }
}

1346. Check If N and Its Double Exist

題目

Input 是一個整數陣列，陣列長度介於2至500之間，陣列元素大小介於-10^3至10^3之間。
Output 是要判斷陣列內是否有兩個元素符合以下條件:

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

解法(Java)

這題我有想到兩個解法，一個是使用HashMap 去儲存看過的元素(key)跟索引(index)，比對的時候乘以2跟除以2都看過一次，O(n)就可以成功；另一個解法是不用任何物件儲存看過的內容，但要跑O(n^2)，這解法就是單純的暴力解阿。

Runtime: 1 ms
Memory Usage: 43.1 MB

class Solution {
    public boolean checkIfExist(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(arr[0], 0);
        
        for (int i = 1, len = arr.length; i < len; i++) {
            if (map.containsKey(arr[i]*2)) {
                if (map.get(arr[i]*2) != i) return true;
            } else if (map.containsKey(arr[i]/2) && arr[i]%2 == 0) {
                if (map.get(arr[i]/2) != i) return true;
            }
            map.put(arr[i], i);
        }
                    
        return false;
        
    }
}

941. Valid Mountain Array

題目

Input 是一個整數陣列，陣列長度介於1至10^4之間，陣列內元素大小介於0至10^4之間。
Output 要一個布林值，如果輸入的整數陣列，元素順序能像山一樣起伏就是true，反之則是false。

Example 1:

Input: arr = [2,1]
Output: false

Example 2:

Input: arr = [3,5,5]
Output: false

Example 3:

Input: arr = [0,3,2,1]
Output: true

解法(Java)

題目其實有個圖片講解，但懶得複製過來就用文字說明吧，反正就是陣列以最大值為分界，前面的元素都要是遞增，後面的都是遞減，如果連續兩個相同元素就算false。

這題一開始就先判斷陣列長度小於2就是false，再來才會看陣列內的元素排列狀況。
而為了判斷陣列內元素是要遞增還遞減，需要一個布林值去判斷，再來就是一堆if-else 判斷這個狀況這個大小是否合理。

Runtime: 2 ms
Memory Usage: 44.6 MB

class Solution {
    public boolean validMountainArray(int[] arr) {
        int len = arr.length;
        if (len <= 2) return false;
        
        boolean down = false;
        for (int i = 0; i < len - 1; i++) {
            int curr = arr[i], next = arr[i + 1];
            if (curr == next) return false; 
            
            if (curr > next) {
                if (!down) {
                    if (i > 0) {
                        down = true;
                    } else return false;
                }
            } else {
                if (down) return false;
            }
        }
        
        return down;
    }
}

小結

不知道是不是老了，前一個禮拜認真刷題一下就想到了，這禮拜純打文章沒動腦重新看一次題目都忘記自己上禮拜怎麼想出解法的，果然人還是要常動腦阿...