题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
成都创新互联公司服务项目包括隆德网站建设、隆德网站制作、隆德网页制作以及隆德网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，隆德网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到隆德省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！
# -*- coding: utf-8 -*-
# @Time : 2019-07-08 21:09
# @Author : Jayce Wong
# @ProjectName : job
# @FileName : getLeastNumbers.py
# @Blog : https://blog.51cto.com/jayce1111
# @Github : https://github.com/SysuJayce
class Solution:
"""
从数组中寻找最小的k个数字，一般来说最直接的做法就是先将这个数组排序，然后取最小的k个数字即可。
但是这样做的时间复杂度为O(nlogn)
解法1：
借鉴快排中partition()的做法，因为partition()每次可以确定一个下标的正确元素，并保证其左右与其
大小关系有序。所以只要我们通过partition()确定了下标为k-1的元素，那么其左边都是小于该元素的。
时间复杂度为O(n)
解法2：
可以维护一个容量为k的容器，然后遍历整个数组，如果遇到比容器中最大值要小的元素，那么就将这个元素
替换容器中的最大值。时间复杂度为O(nlogk)
"""
def GetLeastNumbers_Solution1(self, tinput, k):
if k <= 0 or k > len(tinput):
return []
ans = tinput[:k]
for i in range(k, len(tinput)):
if tinput[i] < max(ans):
ans.remove(max(ans))
ans.append(tinput[i])
return sorted(ans)
def GetLeastNumbers_Solution2(self, tinput, k):
def partition(begin, end):
pos = begin
for i in range(begin, end):
if tinput[i] < tinput[end]:
tinput[i], tinput[pos] = tinput[pos], tinput[i]
pos += 1
tinput[end], tinput[pos] = tinput[pos], tinput[end]
return pos
if k <= 0 or k > len(tinput):
return []
start, stop = 0, len(tinput) - 1
idx = partition(start, stop)
while idx != k - 1:
if idx > k:
stop = idx - 1
else:
start = idx + 1
idx = partition(start, stop)
return sorted(tinput[: k])
def main():
nums = [4, 5, 1, 6, 2, 7, 3, 8]
k = 4
solution = Solution()
print(solution.GetLeastNumbers_Solution2(nums, k))
if __name__ == '__main__':
main()
