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]