Jacky's Blog Jacky's Blog
  • 首页
  • 关于
  • 项目
  • 大事记
  • 留言板
  • 友情链接
  • 分类
    • 干货
    • 随笔
    • 项目
    • 公告
    • 纪念
    • 尝鲜
    • 算法
    • 深度学习
首页 › 算法 › Python 列表合并题

Python 列表合并题

Jacky
10月 28, 2019算法阅读 3,046

完成 merge(L1, L2) 函数:输入参数是两个从小到大排序好的整数列表 L1 和 L2,
返回合成后的从小到大排序好的大列表 X

例如 merge([1,4,5], [2, 7, 11]) 会返回 [1,2,4,5,7]; merge([], [2,3,4]) 会返回 [2,3,4]
[1, 5, 7, 9], [2,4,6]
要求:
(1) 程序中比较两个元素大小的次数不能超过 len(L1) + len(L2)
(2) 只能用列表 append() 和 len() 函数

高中舍友给我发的题

很迷,这道题想了好久,写了好几种解法,然后发布这篇文章之前又改了一次。现在的方案和代码量是我能想到的最优解。

难点在于如何在程序比较两个元素大小的次数不能超过 len(L1) + len(L2) 显然桶排序(o(2*(m+n))、冒泡排序(o(n^2))、快速排序(o(nlogn))统统不能用。好在给定的两个数列都已经排序好了,这里用归并排序。

Python 列表合并题-Jacky's Blog
算法

先来个循环,对两个列表分别计数,每一步都取最小值到新列表,比如取到l1[0] 下一个循环就让 l1[1]跟 l2[0] 比较,以此类推。如果有一个列表全部元素都已经被比较完了并全部加入新列表中了,就直接让另一个列表内的剩下的元素加到新列表后面。

经过这波操作之后,最大比较次数为 len(l1)+len(l2) -1,某些情况下比较次数会降到 1/3[ len(l1)+len(l2) ]

下面是实现的代码

# 时间复杂度 n(n) n < len(1)+len(2)
def merge(l1, l2):
    l1_length = len(l1)
    l2_length = len(l2)
    
    if l1_length is 0:
        return l2
    if l2_length is 0:
        return l1
    
    x = []
    i = 0
    j = 0
    m = 0

    while True:
        m += 1
        if l1[i] < l2[j]:
            x.append(l1[i])
            if i < l1_length - 1:
                i += 1
            else:
                for s in l2[j:]:
                    x.append(s)
                break
        else:
            x.append(l2[j])
            if j < l2_length - 1:
                j += 1
            else:
                for l in l1[i:]:
                    x.append(l)
                break

    print('两个列表的长度和 %s 比较次数 %s' % (l1_length + l2_length, m))
    return x

文章最后修订于 2021年6月23日

Python
赞(4)
本文系作者 @Jacky 原创发布在 Jacky's Blog。未经许可,禁止转载。
在 Xcode 中写 C 程序
上一篇
树莓派首次启动无显示器配置
下一篇
再想想
暂无评论
近期评论
  • Jacky发表在《Nginx UI》
  • daiwenzh5发表在《Nginx UI》
  • Jacky发表在《Nginx UI》
  • daiwenzh5发表在《Nginx UI》
  • Jacky发表在《Nginx UI》
4
  • 4
  • 0
Copyright © 2016-2023 Jacky's Blog. Designed by nicetheme.
粤ICP备16016168号-1
  • 首页
  • 关于
  • 项目
  • 大事记
  • 留言板
  • 友情链接
  • 分类
    • 干货
    • 随笔
    • 项目
    • 公告
    • 纪念
    • 尝鲜
    • 算法
    • 深度学习
# Mac # # Apple # # OS X # # iOS # # macOS #
Jacky
PHP C C++ Python | 舞象之年 | 物联网工程
174
文章
169
评论
267
喜欢