Python3如何合并两个有序数组？本篇文章小编给大家分享一下Python3合并两个有序数组代码实例，小编觉得挺不错的，现在分享给大家供大家参考，有需要的小伙伴们可以来看看。
第一种思路，把两个数组合为一个数组然后再排序，问题又回归到冒泡和快排了，没有用到两个数组的有序性。(不好)
第二种思路，循环比较两个有序数组头位元素的大小，并把头元素放到新数组中，从老数组中删掉，直到其中一个数组长度为0。然后再把不为空的老数组中剩下的部分加到新数组的结尾。(好)
第二种思路的排序算法与测试代码如下：
def merge_sort(a, b):
ret = []
while len(a)>0 and len(b)>0:
if a[0] <= b[0]:
ret.append(a[0])
a.remove(a[0])
if a[0] >= b[0]:
ret.append(b[0])
b.remove(b[0])
if len(a) == 0:
ret += b
if len(b) == 0:
ret += a
return ret
if __name__ == '__main__':
a = [1,3,4,6,7,78,97,190]
b = [2,5,6,8,10,12,14,16,18]
print(merge_sort(a, b))
反思了一下上面的过程，不应该用remove方法，因为仔细想一下remove方法可能比较耗时，不算最简单。
改进一下，改用索引元素比较法替代头位元素比较法：
def merge_sort(a, b):
ret = []
i = j = 0
while len(a) >= i + 1 and len(b) >= j + 1:
if a[i] <= b[j]:
ret.append(a[i])
i += 1
else:
ret.append(b[j])
j += 1
if len(a) > i:
ret += a[i:]
if len(b) > j:
ret += b[j:]
return ret
if __name__ == '__main__':
a = [1,3,4,6,7,78,97,190]
b = [2,5,6,8,10,12,14,16,18]
print(merge_sort(a, b))
这个基本就是最简单的方法了。

 

目录

88. 合并两个有序数组

21. 合并两个有序链表

88. 合并两个有序数组

【题目】：



【代码】：



另外：



21. 合并两个有序链表

【题目】：



【代码】：



 

 

合并两个有序数组
题目
给定两个有序整数数组nums1和nums2，将nums2合并到nums1中，使得nums1成为一个有序数组。

链接：https://leetcode-cn.com/problems/merge-sorted-array/
思路
利用python切片进行合并，合并后用sort函数进行排序
python代码
class Solution:
	def merge(self,nums1: List[int],m:int,nums2:List[int],n,int)->None:
		nums1[m:m+n] = nums2
		nums1.sort()
	


相关知识点
列表的切片   nums1[m:m+n]代表由第m+1个元素到m+n个元素组成的列表

sort函数可以对列表进行排序
执行结果
执行用时 : 40 ms, 在所有 Python3 提交中击败了68.84% 的用户

内存消耗 : 13.5 MB, 在所有 Python3 提交中击败了27.42%的用户

# 合并两个有序数组
# 给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
#
# 说明：
# 初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。
# 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
#
# 示例：
# 输入：
# nums1 = [1,2,3,0,0,0], m = 3
# nums2 = [2,5,6],       n = 3
# 输出：[1,2,2,3,5,6]
#
# 提示：
# -10^9 <= nums1[i], nums2[i] <= 10^9
# nums1.length == m + n
# nums2.length == n
class Solution:
def merge(self, nums1, m, nums2, n):
left = 0
right = 0
for i in range(0,len(nums2)):
num = nums2[i]
ins = -1
c = len(nums1) - n
right = c-1
while left <= right:
mid = (left+right+1)//2
if nums1[mid] <= num and (((mid+1) >= c) or nums1[mid+1] >= num):
ins = mid
left = mid+1
break
elif nums1[mid] <= num:
left = mid+1
else:
right = mid-1
nums1.insert(ins+1,num)
s = Solution()
s.merge([1,2,3],3,[2,5,6],3)
一键复制
编辑
Web IDE
原始数据
按行查看
历史