Leetcode Merge Sorted Array

开始刷Leetcode,希望自己能坚持下来,github全绿。

参考:https://leetcode.com/problems/merge-sorted-array/description/

一、题目

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

其实就是重新组合两个有序数组,组合后的数组也必须有序。

二、解答

这题给出了提示,认为两个数组中的num1数组有足够的空间,要求最后组合的结果就是num1。如果没有“num1数组还有多余的空间”这个前提,我会定义一个外部数组num3,最后组合在num3里(会占用额外的空间)。

个人的解题思路如下:

首先,两个数组初始已经是有序的,默认为从小到大,那么先比较两个数组最后的元素(注意不是尾部,因为num1数组有多余空间,所以我们需要一个参数n指向num1的最后一个元素的index),一定能区分出一个最大的数,放入num1的尾部。接下来依次比较,较大数继续放入,直到某个数组为空(已经放完了),将另外一个数组的元素全部放入即可(因为数组本来就是有序的,所以放入之后也是有序的)。

于是,这道题变成了“不断比较两个数,较大者依次插入”,这需要记录比较的两个元素的位置。首先建立两个指针,指向两个初始数组的最后的元素。哪个初始数组放入了,指针就指向前一个位置(因为是数组,所以直接index-1)。放入组合数组之后,我们要记录下一个数插到组合数组的哪个位置。所以另外建立一个指针,指向组合数组中下个插入的位置(同样-1),指导下个元素要插到哪里。

那么问题来了,为什么要从尾部开始比较?从头开始比较不行吗?

要注意题目的说明是num1有多余的空间(一般指数组后部),如果从头开始比较,就要把最小的数放在数组后部,最后出来的组合数组顺序就变成了从大到小。

具体实现如下:

mergeSortedArrayDay1.java

运行结果为:

那么问题来了,这道题有什么应用场景呢?

个人想到了这样的场景:如果要对一个大容量数组进行排序,可以把这个大数组分成n个小数组,使用多线程分别进行排序,最后再组合成一个有序数组。最后的组合步骤就可以使用这道题目的思路。

三、总结

希望这是一个好的开始(最近用svn比较多,git都用不熟练了…要快点捡回来)。

代码放在github:https://github.com/xie4ever/Leetcode

发表评论

电子邮件地址不会被公开。 必填项已用*标注