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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 |
package com.xie.leetcode.array; import java.util.Arrays; /** * * @author xie4ever * */ public class mergeSortedArrayDay1 { public static void merge(int A[], int m, int B[], int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) { if (A[i] > B[j]) { A[k--] = A[i--]; } else { A[k--] = B[j--]; } } while (j >= 0) { A[k--] = B[j--]; } } public static void main(String[] args) { int A[] = new int[6]; A[0] = 1; A[1] = 2; A[2] = 3; int B[] = new int[] { 2, 3, 6 }; System.out.println(Arrays.toString(A)); System.out.println(Arrays.toString(B)); merge(A, 3, B, 3); System.out.println(Arrays.toString(A)); } } |
运行结果为:
1 2 3 |
[1, 2, 3, 0, 0, 0] [2, 3, 6] [1, 2, 2, 3, 3, 6] |
那么问题来了,这道题有什么应用场景呢?
个人想到了这样的场景:如果要对一个大容量数组进行排序,可以把这个大数组分成n个小数组,使用多线程分别进行排序,最后再组合成一个有序数组。最后的组合步骤就可以使用这道题目的思路。
三、总结
希望这是一个好的开始(最近用svn比较多,git都用不熟练了…要快点捡回来)。
代码放在github:https://github.com/xie4ever/Leetcode