python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路-Toy模板网

这篇具有很好参考价值的文章主要介绍了python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

一.需求:

给你两个按非递减顺序排列的整数列表nums1和nums2，另有两个整数m和n，分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
注意:最终，合并后数组不应由函数返回，而是存储在数组nums1中。为了应对这种情况，nums1的初始长度为m+n，其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n

二.示例测试

示例1:
输入: nums1 = [1,2,3,0,0,0]，m = 3，nums2 = [2,5,6]，n =3
输出:[1,2,2,3,5,6]
解释:需要合并[1,2,3]和[2,5,6] 。
合并结果是 [1,2,2,3,5,6]，其中斜体加粗标注的为nums1 中的元素。

示例2:
输入:nums1 = [1]，m = 1，nums2 = [，n = o输出:[1]
解释:需要合并[1]和[] 。合并结果是[1] 。

示例3:
输入: nums1 = [0]，m = 0，nums2 = [1]，n = 1输出:[1]
解释:需要合并的数组是[]和[1]。合并结果是[1]。
注意:因为 m = 0 ，所以nums1中没有元素。nums1中仅存的0仅仅是为了确保合并结果可以顺利存放到nums1 中。

三.实现流程图

python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路
第一轮循环,p1,p2=0比较2和1的大小,list2的第一个元素更小,把list2的第一个元素放到sorted里面去,此时的指针p2
要向后移一位变成1

第二轮循环,p1=0,p2=1比较2和3的大小,list1的第一个元素更小,把list1的第一个元素放到sorted里面去,此时的指针p1要往后移一位变成1
python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路
第三轮循环,p1=1,p2=1比较4和3的大小,p2指向的list2元素更小,把list2中p2指向的元素放到sorted里面去,此时的指针p2要往后移一位变成2

第四轮循环,p1=1,p2=2比较4和9的大小,p1指向的list1元素更小,把list1中p1指向的元素放到sorted里面去,此时的指针p1要往后移一位变成2
python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路
第五轮循环,p1=2,p2=2比较4和9的大小,p1指向的list1元素更小,把list1中p1指向的元素放到sorted里面去,此时的指针p1要往后移一位变成3

第五轮循环,p1=3,p2=2比较4和9的大小,p1指向的list1元素更小,把list1中p1指向的元素放到sorted里面去,此时的指针p1要往后移一位变成4
python实现+leetcode题+合并两个有序列表超详细流程图分析以及代码思路
第六轮排序,此时的p1等于list1的长度,说明list1已经遍历完成了,那么此时就直接把list2剩下的元素追加到sorted中去

四.代码实现

nums1 = [2, 4, 5, 8]  # 这里的0是占的位置
nums2 = [1, 3, 9]
m = 4  # nums的长度
n = 3  # nums2的长度
p1, p2 = 0, 0  # 定义两个指针索引
def sorted_merge(nums1, nums2, m, n, p1, p2):
    sorted = []  # 遍历之后的结果
    while p1 < m or p2 < n: 
        if p1 == m:
            sorted.append(nums2[p2])
            p2 += 1
        elif p2 == n:
            sorted.append(nums1[p1])
            p1 += 1
        elif nums1[p1] < nums2[p2]:
            sorted.append(nums1[p1])
            p1 += 1
        else:
            sorted.append(nums2[p2])
            p2 += 1
    print(sorted)
    nums1[::] = sorted
    print(nums1)


sorted_merge(nums1, nums2, m, n, p1, p2)

五.代码思路

首先需要创建一个新的列表来存储遍历排序的结果,定义两个指针p1和p2用来控制列表的遍历,而那个while循环的条件就是为了让两个元素个数不同的列表能够都遍历完所有元素,如果list1或者list2其中一个列表元素已被遍历排序完,而另一个列表还存有元素,那么就可以把另一个列表剩下的元素直接追加到我们的sorted存放最终结果的列表中去,最后因为它需要把合并后的结果放到nums1中,所以我们这里直接使用列表的切片方式对nums1从头到尾进行切片,相当于将sorted深拷贝给nums1