1、算法描述：
有两个有序的整型数组arrayA，和arrayB，先要将它俩合并得到新的合并数组同样是有序的。
示例：
arrayA = [0, 1 , 3 , 4 , 6] //count = 5
arrayB = [2 , 3, 3 , 6 , 8 , 9 , 10] //count = 7
合并后：
array = [0, 1, 2, 3, 3, 3, 4, 6, 6, 8, 9, 10]
2、解答思路：
1）、非法判定：
对于非法输入进行返回；
2）、合法输入：
将两个数组都按从后往前（或者从前往后）一个元素一个元素取出进行比较
设置两个索引indexA和indexB，分别表示数组A和B当前取出的元素，进行比较，当某一个索引小于0，即下次访问要发生数组越界，此时一个数组所有元素已经全部比较完毕，但是另一个数组此时可能还有元素没有参加比对，多出的这些元素直接拼接到合并的数组里面。
3、实现：
class MergeTwoOrderedArrays {
func merge(arr1 : [Int] , arr2 : [Int]) -> [Int]? {
var indexA : Int = arr1.count - 1
var indexB : Int = arr2.count - 1
//合法判定
if indexA < 0 {
return arr2;
} else if indexB < 0 {
return arr1;
}
//生成存放数据的数组，注意此时的index并不是数组A元素个数加数组B元素个数，而是要减一
var indexC : Int = indexA + indexB + 1 //index要比数组大小小1
var array : [Int] = [Int](repeating: 0, count: indexC + 1) //count为数组A元素个数加数组B的元素个数
while ( indexA >= 0 && indexB >= 0 ) {//判定哪个数组元素最先比较完成
if arr1[indexA] > arr2[indexB] {
array[indexC] = arr1[indexA]
indexC -= 1
indexA -= 1
}
else {
array[indexC] = arr2[indexB]
indexC -= 1
indexB -= 1
}
}
while indexA >= 0 {//多余元素拼接
array[indexC] = arr1[indexA]
indexC -= 1
indexA -= 1
}
while indexB >= 0 {//多余元素拼接
array[indexC] = arr2[indexB]
indexC -= 1
indexB -= 1
}
return array
}
}
//测试
let test = MergeTwoOrderedArrays()
test.merge(arr1: [0, 1 , 3 , 4 , 6], arr2: [2 , 3, 3 , 6 , 8 , 9 , 10])
//结果
[0, 1, 2, 3, 3, 3, 4, 6, 6, 8, 9, 10]
上面使用的是从后往前一个一个遍历比较的方法，当然也可以从前往后一个一个遍历比较，看谁先到达数组的结尾。
4、分析：
1）、时间复杂度：
while ( indexA >= 0 && indexB >= 0 )
循环最多循环次数是m+n次，所以时间复杂度为O(n)
2）、空间复杂度：
需要零时占用的空间为m+n，所以空间复杂度为O(n)
网友评论