Leetcode Merge Sorted Array 2017年11月29日
未分类
0 条评论

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

Post Views: 53