88. Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array

這是一個很經典也很簡單的題目，目的是要將兩個已經排序好的陣列合成一個排序好的大陣列。

題目描述中有說到這是兩個 non-decreasing 的陣列，也就是 non-strictly increasing。排序好的陣列是我們很喜歡的簡單題目，因為我們只要根據需求比頭比尾就好了，當 a_n > b_n，我們可以假定 a_n 會大於 b 陣列的所有數字，因為 b_n 已經是 b 陣列裡的最大值了。依此類推，這一題我的解法就是從尾巴開始比較，依序填進 nums1 尾巴開始的陣列裡。我的答案如下：

class Solution {
public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

		int n_1 = m - 1, n_2 = n - 1;
		
		for (int i = m + n - 1; i >= 0; i--) {

			if (n_1 < 0 || n_2 < 0)
				break;
			if (nums1[n_1] > nums2[n_2]) {
				nums1[i] = nums1[n_1];
				n_1--;
			} else {
				nums1[i] = nums2[n_2];
				n_2--;
			}

		}

		for (int j = n_2; j >= 0; j--) {
			nums1[j] = nums2[j];
		}
	}
};

Best Solution

TODO