未分類

Merge Sorted Array

Array, Go, LeetCode, TwoPointers

Merge Sorted Array

GGiven 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.

提示 解題應用
Array 每格儲存值整體位移
TwoPointers 記錄Array位移位置

Default:

1
2
3
func merge(nums1 []int, m int, nums2 []int, n int) {
}

解答思路:

先前也有類似的題目，只是當時是Linked List，這次是用Array來處理，麻煩上來說Array並不比Linked List輕鬆，既然已經告訴你第一個Array已經有足夠的長度就意味著你不需要新增新的陣列來儲存，也就是說當該陣列在前面新增一個值時，你需要將後頭的值一個個向後移，這會浪費不少時間在處理位移，唯一的優點就是取值時不再需要遍歷，而重點就是需要幾個flag來紀錄第一個陣列的開頭index與尾巴index和第二個陣列的開頭index，

程式碼解說:

第一個陣列結尾的index值最為重要，因為第二個陣列的值是要插入第一個陣列排序，這意味著當值依大小放入第一個陣列之中時，在該值後頭原本就在的資料就要依序往後挪一格讓該值有空間存放，而移動時則是從原本第一陣列最後頭有資料的那格開始移問題會最小，而隨著前面資料的增加理所當然結尾的index值也會跟著變大，再加上如果接下來要插入的值都比第一個陣列的所有資料都大，也需要知道第一個陣列結尾的index在哪才能夠將剩餘的值依續往該index後頭放，而至於兩個陣列開頭的index則是記錄目前值的大小已經比較到哪裡，用於將要插入的值準確的放入大小有序的陣列之中

1
2
3
flag1 := 0
flag1e := m - 1
flag2 := 0

利用一回圈來逐步比較兩陣列值的大小來尋求插入點，原則上來說當第一個陣列的長度遍歷等於所有資料長度時，會與第二個陣列遍歷的資料同時達成(畢竟是第二個陣列的資料已經全塞入第一個陣列之中了)，不過這邊還是寫成達成其一條件就結束迴圈，而正如先前所說當插入值在第一個陣列尋找比其大的值，比其小第一個陣列就繼續往下一個走直到發現較大值的位置，再來就將資料放在該值的前面，這時就需要再一個迴圈從陣列最後的index將資料一個個向後移以多出一格空間，隨著值放入之後，最後的index值當然也會跟著變大，而第二個陣列因為已經將值放入，自然就找下一個值準備再插入，直到要插入的點已經超過第一個陣列尾巴index值的下一個(意味著目前插入的值已經都比第一個陣列的所有資料來的大)，那最後就只要將第二個陣列中其餘的資料依序往後頭放即可結束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for true {
	if flag1 == m+n || flag2 == n {
		break
	} else if nums1[flag1] >= nums2[flag2] {
		for i := flag1e; i >= flag1; i-- {
			nums1[i+1] = nums1[i]
		}
		nums1[flag1] = nums2[flag2]
		flag1e++
		flag2++
	} else if flag1 == flag1e+1 {
		for j := flag2; j < n; j++ {
			nums1[flag1] = nums2[j]
			flag1++
		}
		break
	} else {
		flag1++
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func merge(nums1 []int, m int, nums2 []int, n int) {
	flag1 := 0
	flag1e := m - 1
	flag2 := 0
	for true {
		if flag1 == m+n || flag2 == n {
			break
		} else if nums1[flag1] >= nums2[flag2] {
			for i := flag1e; i >= flag1; i-- {
				nums1[i+1] = nums1[i]
			}
			nums1[flag1] = nums2[flag2]
			flag1e++
			flag2++
		} else if flag1 == flag1e+1 {
			for j := flag2; j < n; j++ {
				nums1[flag1] = nums2[j]
				flag1++
			}
			break
		} else {
			flag1++
		}
	}
}

總結:

兩大小有序的陣列要做合併時，需要記錄三個值，分別是兩陣列的開頭index用於表示目前兩陣列值大小比較後的位置以尋求插入點，而第三個值最為重要，記錄著第一個要合併陣列的index值，用於當值插入陣列前方時需要從最後頭將原資料一個個向後移動以空出新位置，此外當插入的點已經超過第一個陣列尾巴index值的下一個，意味著目前插入的值已經比第一個陣列的所有資料來的大，這時僅需將其餘的資料依序往後頭放即可。

分享到