生鱼忧患 死鱼安乐

Leetcode88

 leetcode  408  1 分钟

88. 合并两个有序数组

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 num1 成为一个有序数组。

说明:

  • 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
  • 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

1
2
3
4
5

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

思路

从nums1的最后一个位置(i=len(nums1)-1)开始依次填入两个数组中最大的;

因为两个数组都是有序的,所以只需要从最后的位置比较即可;

nums1与nums2比较下标为m-1和n-1,将两者中较大的移到nums1的尾部;

将取出数字的数组下标(m或者n)和i都往前移动一步,直到nums2取完.

若nums1的m<0,则只需要将nums2的剩余数字依次填充到i下标即可

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

func merge(nums1 []int, m int, nums2 []int, n int) {
	if m == 0 {
		copy(nums1, nums2)
		return
	}
	m--
	n--
	for i := len(nums1) - 1; i >= 0 && n >= 0; i-- {
		if m < 0 || nums1[m] <= nums2[n] {
			nums1[i] = nums2[n]
			n--
            continue
		}
		if nums1[m] > nums2[n] {
			nums1[i], nums1[m] = nums1[m], nums2[n]
			m--
		}
	}
}
updatedupdated2021-07-122021-07-12

相关文章：

加载评论