对两个有序的数组进行合并

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)

5、联系方式

上一篇下一篇

猜你喜欢

热点阅读