88. Merge Sorted Array

Leetcode 問題: 88. Merge Sorted Array
Categories:
Tags:

題目

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

合併 2 個排序過的整數陣列為一個陣列

答案

Golang

func merge(numberList1 []int, list1ElementCount int, numberList2 []int, list2ElementCount int) []int {
	// 總數字個數
	totalElementCount := list1ElementCount + list2ElementCount

	for list1ElementCount > 0 && list2ElementCount > 0 {
		// 當其中一清單還有資料
		// 將較大的數字設定在「清單1」最後方
		if numberList1[list1ElementCount-1] <= numberList2[list2ElementCount-1] {
			// 「清單1」數字小於或等於「清單2」
			// 「清單1」最後面設定為「清單 2」數字
			numberList1[totalElementCount-1] = numberList2[list2ElementCount-1]
			list2ElementCount--
		} else {
			// 「清單1」數字大於「清單2」
			// 「清單1」最後面設定為「清單 1」數字
			numberList1[totalElementCount-1] = numberList1[list1ElementCount-1]
			list1ElementCount--
		}
		// 繼續處理下一個數字
		totalElementCount--
	}

	// 避免「清單2」資料沒有處理完，而「清單1」的數字已經更新到陣列中，所以剩下的「清單2」數字皆為較小的數字，所以直接覆蓋數字即可
	for ; list2ElementCount > 0; list2ElementCount-- {
		numberList1[list2ElementCount-1] = numberList2[list2ElementCount-1]
	}

	return numberList1
}

完整程式碼

package main

import (
	"fmt"
)

type Question struct {
	// 參數
	Parameter
	// 答案
	Answer
}

// 參數
type Parameter struct {
	numberList1       []int
	list1ElementCount int
	numberList2       []int
	list2ElementCount int
}

// 答案
type Answer struct {
	result []int
}

func main() {

	QuestionList := []Question{
		{
			Parameter{[]int{1, 2, 3, 0, 0, 0}, 3, []int{2, 5, 6}, 3},
			Answer{[]int{1, 2, 2, 3, 5, 6}},
		},
		{
			Parameter{[]int{0}, 0, []int{1}, 1},
			Answer{[]int{1}},
		},
	}

	fmt.Printf("------------------------Leetcode Problem 88------------------------\n")
	for _, question := range QuestionList {
		param := question.Parameter
		expectAnswer := question.Answer
		exactAnswer := merge(param.numberList1, param.list1ElementCount, param.numberList2, param.list2ElementCount)
		fmt.Printf("【input】:%v       【output】:%v     【expect】:%v\n", param, exactAnswer, expectAnswer.result)
	}
}

func merge(numberList1 []int, list1ElementCount int, numberList2 []int, list2ElementCount int) []int {
	// 總數字個數
	totalElementCount := list1ElementCount + list2ElementCount

	for list1ElementCount > 0 && list2ElementCount > 0 {
		// 當其中一清單還有資料
		// 將較大的數字設定在「清單1」最後方
		if numberList1[list1ElementCount-1] <= numberList2[list2ElementCount-1] {
			// 「清單1」數字小於或等於「清單2」
			// 「清單1」最後面設定為「清單 2」數字
			numberList1[totalElementCount-1] = numberList2[list2ElementCount-1]
			list2ElementCount--
		} else {
			// 「清單1」數字大於「清單2」
			// 「清單1」最後面設定為「清單 1」數字
			numberList1[totalElementCount-1] = numberList1[list1ElementCount-1]
			list1ElementCount--
		}
		// 繼續處理下一個數字
		totalElementCount--
	}

	// 避免「清單2」資料沒有處理完，而「清單1」的數字已經更新到陣列中，所以剩下的「清單2」數字皆為較小的數字，所以直接覆蓋數字即可
	for ; list2ElementCount > 0; list2ElementCount-- {
		numberList1[list2ElementCount-1] = numberList2[list2ElementCount-1]
	}

	return numberList1
}

參考資料