对两个有序的数组进行合并
2018-01-13 本文已影响34人
SuAdrenine
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)