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
}

参考资料