题目：
合并两个排序的整数数组A和B变成一个新的数组。
样例
给出A=[1,2,3,4]，B=[2,4,5,6]，返回 [1,2,2,3,4,4,5,6]
挑战
你能否优化你的算法，如果其中一个数组很大而另一个数组很小？
解题：
利用Java的ArrayList很简单的，时间复杂度O(n+m)两个数组都要遍历一遍，对应两个数组长度差别很大的情况，效率就低了
Java程序：
class Solution {
/**
* @param A and B: sorted integer array A and B.
* @return: A new sorted integer array
*/
public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
// write your code here
ArrayList merge = new ArrayList();
int aSize = A.size();
int bSize = B.size();
int i=0;
int j = 0;
while(i<aSize && j<bSize){
if(A.get(i)<=B.get(j)){
merge.add(A.get(i));
i++;
}else{
merge.add(B.get(j));
j++;
}
}
while(i<aSize){
merge.add(A.get(i));
i++;
}
while(j<bSize){
merge.add(B.get(j));
j++;
}
return merge;
}
}
总耗时: 1832 ms
这个好无节操的哦
class Solution {
/**
* @param A and B: sorted integer array A and B.
* @return: A new sorted integer array
*/
public ArrayList<Integer> mergeSortedArray(ArrayList<Integer> A, ArrayList<Integer> B) {
// write your code here
int bSize = B.size();
for(int i=0;i<bSize;i++)
A.add(B.get(i));
Collections.sort(A);
return A;
}
}
总耗时: 1340 ms
Python程序：
Python也可以无节操的来
class Solution:
#@param A and B: sorted integer array A and B.
#@return: A new sorted integer array
def mergeSortedArray(self, A, B):
# write your code here
A = A + B
A.sort()
return A
总耗时: 454 ms
当然也可以复杂的来了
class Solution:
#@param A and B: sorted integer array A and B.
#@return: A new sorted integer array
def mergeSortedArray(self, A, B):
# write your code here
C = []
aLen = len(A)
bLen = len(B)
i = 0
j = 0
while i<aLen or j <bLen:
if (i<aLen and j<bLen):
if A[i] <= B[j] :
C.append(A[i])
i+=1
else:
C.append(B[j])
j+=1
if i==aLen and j<bLen :
C.append(B[j])
j+=1
if i<aLen and j==bLen:
C.append(A[i])
i+=1 return C
总耗时: 314 ms