描述

合并两个有序升序的整数数组A和B变成一个新的数组。新数组也要有序。

样例

样例1：

输入: A=[1], B=[1]
输出:[1,1]	
样例解释: 返回合并后的数组。

样例2：

输入: A=[1,2,3,4], B=[2,4,5,6]
输出: [1,2,2,3,4,4,5,6]	
样例解释: 返回合并后的数组。

挑战

你能否优化你的算法，如果其中一个数组很大而另一个数组很小？

编程语言：Java

解题思想：

1.创建一个新数组，长度为A数组长度+B数组长度。

2.逐一赋值。

3.冒泡排序。

时间复杂度：O(n^2)

IDE代码如下：

package LintCode_Easy;
 
import java.util.Arrays;
 
public class _6 {
 
	public static void main(String[] args) {
		int[] A = new int[] {1,2,3,4};
		int[] B = new int[] {2,4,5,6};
		int[] C = new int[A.length+B.length];
		int swap = 0;
		for(int i=0;i<A.length;i++)
			C[i]=A[i];
		for(int i=A.length,j=0;j<B.length;i++,j++)	//C的起始索引=A的长度
			C[i]=B[j];
		for(int i=0;i<C.length;i++)
			for(int j=i;j<C.length;j++)
			{
				if(C[i]>C[j])
				{
					swap=C[j];
					C[j]=C[i];
					C[i]=swap;
				}
			}
		System.out.println(Arrays.toString(C));
	}
 
}

LintCode编辑器代码如下：

public class Solution {
    public int[] mergeSortedArray(int[] A, int[] B) {
        int[] C = new int[A.length+B.length];
        int swap = 0;
		for(int i=0;i<A.length;i++)
			C[i]=A[i];
		for(int i=A.length,j=0;j<B.length;i++,j++)
			C[i]=B[j];
		for(int i=0;i<C.length;i++)
			for(int j=i;j<C.length;j++)
			{
				if(C[i]>C[j])
				{
					swap=C[j];
					C[j]=C[i];
					C[i]=swap;
				}
			}
			return C;
    }
}