题目分析

1. 题目给出我们n个数字
2. 我们要对n个数字进行排序，并且最终输出前k个最小的数字

方法一：调用库函数

• 实现思路
  • 首先整理输入数据成列表或变量等
  • 然后进行排序
  • 按序输出前k个结果即可

while True:
    try:
        n,k = map(int, input().split())                    # 返回迭代器
        nums = list(map(int, input().split()))             # 返回数组
        nums.sort()                                        # 排序
        print(" ".join(map(str, nums[:k])))                # 组织成输出
    except:
        break

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，由于库函数中sort函数采用快速排序的方式，因此时间代价在这个量级
• 空间复杂度：$O(1)O(1)$，只有常量级别的空间代价开销

方法二：选择排序

• 实现思路

  • 我们对于前k个数组元素进行操作

  • 每次对第i个元素遍历到的时候，往后继续遍历，挑出最小值与位置i的元素交换

  • 最终输出前k个元素即可

while True:
    try:
        n,k = map(int, input().split())                    # 返回迭代器
        nums = list(map(int, input().split()))             # 返回数组
        for i in range(k):                                 # 对前k个元素进行遍历
            mn = nums[i]                                   # 存储当前第i个元素
            pos = i                                        # 存储索引
            for j in range(i+1, len(nums)):                # 从i后面的元素中挑选最小值和位置i交换
                if nums[j] < mn:
                    mn = nums[j]
                    pos = j
            nums[pos] = nums[i]
            nums[i] = mn        
        print(" ".join(map(str, nums[:k])))                # 组织成输出前k个
    except:
        break

复杂度分析

• 时间复杂度：$O(kn)O(kn)$，我们只要挑选k次最小的元素即可，但是每次都需要遍历一遍整个数组
• 空间复杂度：$O(1)O(1)$，只有常量空间代价的开销