手机版 | 登陆 | 注册 | 留言 | 设首页 | 加收藏
当前位置: 网站首页 > python教程 > 文章 当前位置: python教程 > 文章

python题目在线解答计算机二级python题目来源少儿编程python题目

时间:2022-08-03    点击: 次    来源:网络    作者:佚名 - 小 + 大

python题目在线解答计算机二级python题目来源少儿编程python题目


下载地址

https://share.weiyun.com/OvviwGnZ


资料目录
Python练习集100题
100道Python面试题
Python100经典练习题
Python经典题目100道题
Python题库(已收录100道真题)
Python100例视频讲解课程
菜鸟教程Python教程100例
130道python练习题,涵盖基础内容的方方面面
Python考试题复习知识点试卷试题
PYTHON测试题和答案
python第一阶段考试题
Python经典面试题和答案解析
python期末考试复习试卷
python习题集大全(附答案解析)
老男孩Python全栈7期练习题(面试真题模拟)
尚观python第一阶段考试(面试真题模拟)
《Python程序设计基础与应用》习题答案
《Python快速编程入门》——课后题答案
Python编程基础张健 , 张良均课后习题及答案
Python程序设计基础及实践(慕课版)郭炜习题答案
Python程序设计基础习题答案与分析
python基础试题(含答案)

举例

两个有序数组中找第k大的数
题目要求
已知有两个从小到大的有序数组,求两个数组的第k大的数。
[1, 4, 6, 8, 12, 15, 18, 20, 28, 29]
[2, 5, 7, 10]
第8大的数是10
思路分析
两个数组都有序,那么就利用这个有序的特点来解决这个问题。假设数组分别是a b,令middle = k/2, middle_ex = k - middle。比较a[middle]和b[middle]的值。
如果a[middle - 1] == b[middle_ex - 1],那么a[middle-1]不正好是第k大的数么,因为 k= middle_ex + middle,且两个数组都有序。
如果a[middle - 1] < b[middle_ex - 1],让a = a[middle:],前面的那些元素都可以舍弃了, 问题转变成从a 和 b这两个数组里找到第 k - middle 大的值
如果a[middle - 1] > b[middle_ex - 1],让b = b[middle_ex:],前面那些元素都可以舍弃了,问题转变成从a 和 b这两个数组里找到第 k - middle_ex大的值
为什么在取值时用的索引是middle - 1呢,其实原因很简单,我们要找第k大的数,k最小是1,你不能说取第0大的数,我们日常是从1开始计数的,而计算机是从0开始计数的,middle = k/2, 从k计算而来,因此在使用索引时要减 1 。
有几个需要关注的地方
1. 要让数组长度更小的为a
2. 计算middle时,其实要考虑middle是否比a的长度小,不然取a[middle-1]时就出错了,计算middle和 middle_ex为的是从a, b 两个数组里各自找到第middle大和第middle_ex大的两个数,通过比较他们的大小,决定舍弃哪一部分
3. 不断的舍弃,不断的修改k的值,最后,一定会出现k==1的情况,这时,返回min(a[0], b[0])
示例代码
# coding=utf-8


def find_kth(left_lst, left_len, right_lst, right_len, k):
    """
    从left_lst 和 right_lst中寻找第k大的数
    :param left_lst: 长度小的那个数组
    :param left_len:
    :param right_lst: 长度达的那个数组
    :param right_len:
    :param k:
    :return:
    """
    # 确保left_lst长度小于 right_lst 长度
    if left_len > right_len:
        return find_kth(right_lst, right_len, left_lst, left_len, k)

    # 长度小的数组已经没有值了,从right_lst找到第k大的数
    if left_len == 0:
        return right_lst[k-1]

    # 找到第1 大的数,比较两个列表的第一个元素,返回最小的那个
    if k == 1:
        return min(left_lst[0], right_lst[0])

    # k >> 1 ,其实就是k/2
    middle = min(k >> 1, left_len)
    middle_ex = k - middle
    # 舍弃left_lst的一部分
    if left_lst[middle-1] < right_lst[middle_ex-1]:
        return find_kth(left_lst[middle:], left_len-middle, right_lst, right_len, k-middle)
    # 舍弃right_lst 的一部分
    elif left_lst[middle-1] > right_lst[middle_ex-1]:
        return find_kth(left_lst, left_len, right_lst[middle_ex:], right_len-middle_ex, k-middle_ex)
    else:
        return left_lst[middle-1]


if __name__ == '__main__':
    left_lst = [1, 4, 6, 8, 12, 15, 18, 20, 28, 29]
    right_lst = [2, 5, 7, 10]
    k = 8
    print find_kth(left_lst, len(left_lst), right_lst, len(right_lst), k)

    # 合并后排序,找第k大的数
    lst = left_lst + right_lst
    lst.sort()
    print lst[k-1]

上一篇:python题目汇总高一python题目及答案高中信息技术Python题目文档

下一篇:没有了

推荐阅读
声明 | 联系我们 | 关于我们
备案ICP编号  |   QQ:2151239526  |  地址:北京市东城区  |  电话:16605168200  |