[LeetCode] 88. Merge Sorted Array

轉自LeetCode

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

<Solution>

這題先了解一下題意

一開始，nums1 有 m 個元素，nums2 有 n 個元素，而 nums1.size() >= (m+n)

當把 nums2 合併到 nums1 後，最後 nums1.size() 要等於 m+n

舉個測資

nums1 = [-1,-1,0,0,0,0]
m = 4
nums2 = [-1,0]
n = 2

從這邊可以看到，nums1 裡面的 0 有可能是無意義，也可能是真的值

[-1,  -1,  0,  0,  0,  0]，後面兩個是無意義的，純粹只是用來擴充 nums1 的 size

最後要求出來得答案是 [-1, -1, -1, 0, 0, 0]，長度是 m+n = 4+2 = 6

有以上概念後，解題想法如下(參考資料)

• 因為題目有說 num1.size() >= (m+n)，所以可以從後面開始填起，也就是從 index = m + n - 1 開始往前 merge，數字是由大到小

• 因為是從後面開始填起，且 nums1 和 nums2 都是 sorted array，所以每次填的值就是 num1 和 nums2 目前比較大的值，這樣 merge 之後也會是 sorted array

• 這邊會有兩種狀況

• 如果 nums1 裡面有數字比 nums2 小，那麼當 nums2 都填進去 nums1 後，也就結束了，因為前面就是原本的 nums1 比較小的數

• 如果 nums2 裡面的數字有比 nums1 小的，因為我們是要把 nums2 merge 到 nums1，代表當 nums1 都歷遍完之後，nums2 還有值沒有merge，所以這時候就把 nums2 全部填進去剩下的位置

code 如下
c++

	class Solution {
	public:
	void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
	int finalIdx = m + n - 1;
	--m;
	--n;
	while(m >= 0 && n >= 0) {
	nums1[finalIdx--] = (nums1[m] > nums2[n]) ? nums1[m--] : nums2[n--];
	}
	while(n >= 0) {
	nums1[finalIdx--] = nums2[n--];
	}
	}
	};

view raw mergeTwoSortedArray.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
	var index = m + n - 1
	var index1 = m - 1
	var index2 = n - 1
	while(index1 > -1 && index2 > -1) {
	nums1[index--] = if(nums1[index1] >= nums2[index2]) nums1[index1--] else nums2[index2--]
	}
	while(index2 > -1) {
	nums1[index--] = nums2[index2--]
	}
	}
	}

view raw merge_sorted_array.kt hosted with ❤ by GitHub