本节主要解决两个有序数组的合并问题,即将两个有序数组合二为一,成为一个仍然有序的数组.
问题描述:
给定两个有序数组array1和array2,将array2合并进array1成为一个新的数组,使新数组仍为一个有序数组.初始化array1和array2的元素数量分别为a和b.
变量如下:
array1,array2变量:表示输入的两个有序数组
array_变量:表示将array1前a位保存为新的数组
p1变量:表示指向array1的指针,初始值为0
p2变量:表示指向array2的指针,初始值为0
完整代码如下:
def mergetwoarray(self, array1, a, array2, b):# 取array1的前a个元素array_ = array1[:a]# 初始化两个指针p1和p2，分别指向array1和array2的当前比较元素p1 = p2 = 0# 循环直到array1或array2中的元素全部被比较完毕while (p1 < a and p2 < b):# 如果array1中的当前元素小于array2中的当前元素，则将array1的元素添加到array1的末尾if array_[p1] < array2[p2]:array1.append(array_[p1])p1 += 1# 否则，将array2的元素添加到array1的末尾else:array1.append(array2[p2])p2 += 1# 如果array1中还有未比较的元素，则将它们添加到array1的末尾if p1 < a:array1[p1 + p2:] = array_[p1:]# 如果array2中还有未比较的元素，则将它们添加到array1的末尾if p2 < b:array1[p1 + p2:] = array2[p2:]# 返回合并后的array1return array1
