博客

给定两个升序排列的数字数组合并成一个新的升序排列的数字数组。

一、简单版本。

思路：先将两个数组进行合并，然后再进行升序排列

实现：

function merge(arr: number[], arr1: number[]) {
	if (!Array.isArray(arr) || !Array.isArray(arr1)) {
		return []
	}
	const data = arr.concat(arr1)
	data.sort((a, b) => a - b)
	return data
}

优点：思路清晰、代码简单；

二、进阶版本

思路：两个有序数组看成放两排的数字，两排数组各有一个指针，比较两个指针对应位置的元素大小，哪个指针对应的元素小，则把此元素推入返回数组，同时此指针后移一位，如果两个元素相等则两个元素同时推入返回数组，并且两个指针同时往后移一位，如此循环往复，两个指针依次往后推移，当两个数组的指针同时指到数组最后一位加1的时候停止，或者其中一个指针已经到达最后一位加1的时候停止，并且把另一个数组指针后面的元素推入返回数组。

实现：

function merge(arr: number[], arr1: number[]) {
	if (!Array.isArray(arr) || !Array.isArray(arr1)) {
		return []
	}
	if (arr.length === 0) {
		return arr1
	}
	if (arr1.length === 0) {
		return arr
	}
	let firstIndex = 0
	let secondIndex = 0
	const data: number[] = []
	for (let i = 0; i < arr.length + arr1.length; i++) {
		if (arr[firstIndex] > arr1[secondIndex]) {
			data.push(arr1[secondIndex])
			secondIndex += 1
		} else if (arr[firstIndex] < arr1[secondIndex]) {
			data.push(arr[firstIndex])
			firstIndex += 1
		} else if (arr[firstIndex] === arr1[secondIndex]) {
			data.push(arr[firstIndex])
			data.push(arr1[secondIndex])
			secondIndex += 1
			firstIndex += 1	
		}
		if (secondIndex === arr1.length && firstIndex < arr.length) {
			data.push(...arr.slice(firstIndex))
			break
		}
		if (firstIndex === arr.length && secondIndex < arr1.length) {
			data.push(...arr1.slice(secondIndex))
			break
		}
		if (firstIndex === arr.length && secondIndex === arr1.length) {
			break
		}
	}
	return data
}

优点：复杂度低，时间复杂度O(n)