题目描述
输入 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()
来源: http://www.bubuko.com/infodetail-3118005.html