每日leetcode——JZ40 最小的K个数
题目
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
【每日leetcode——JZ40 最小的K个数】要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)
输入：
[4,5,1,6,2,7,3,8],4
返回值：
[1,2,3,4]
说明：
返回最小的4个数即可，返回[1,3,2,4]也可以输入：
[1],0
返回值：
[]输入：
[0,1,2,1,2],3
返回值：
[0,1,1]思路 第一时间想到的做法是，利用排序算法，将整个数组从小到大排序，然后选取前k个数，就是该数组的最小的k个数了。
但是，这个做法不是最优的。题目只要求返回最小的k个数，并不要求这k个数也要按顺序排好。所以要好好利用这个条件。
更高效的思路是，利用快速排序的思想，通过基准值，将数组分成小于基准值部分、大于等于基准值部分。只是大体上划分出了较小的部分、和较大的部分，并没有对每个数值都进行排序，这也正好符合题目的条件。
所以，我们利用快速排序的思路：
- 如果小于基准值部分的元素刚好是k个，那么就直接得出了结果
- 如果小于基准值部分的元素多余k个，那么就在小于部分再去执行快排，直到较小部分刚好是k个
- 如果小于基准值部分的元素少于k个，那么就在大于部分去执行快排，直到新的较小部分加上之前的较小部分刚好是k个
def GetLeastNumbers_Solution(input, k):
def quickSort(nums,left,right,index):
# 数组进入快排操作，返回快排后的基准值索引
mid = partition(nums,left,right)
# 如果基准值索引 刚好等于 k，说明基准值前面的数，刚好是最小的k个数
if mid==index:
return nums[:index]
# 如果基准值索引 > k，说明当前较小部分的个数多于k个，较小部分继续快排
# 直到mid==index，刚好找到k个最小的数，将结果一层层向上返回
elif mid > index:
return quickSort(nums,left,mid-1,index)
# 如果基准值索引 < k，说明当前较小部分的个数少于k个，还有部分最小k个数在较大部分中
# 较大部分进入快排，当mid==index时，mid前面就是最小的k个数，将结果一层层向上返回
else:
return quickSort(nums,mid+1,right,index)
# 快排操作
def partition(nums,left,right):
# 基准值
pivot = nums[left]while left=pivot:
right-=1nums[left]=nums[right]while left 推荐阅读
- MySQL|MySQL — 数据查询语言
- Vue|Vue 响应式原理剖析 —— 数据更新常见问题
- ros编程实战|北邮智能车仿真培训（八）—— 两轮摄像头平衡车
- 【ASP.NET|【ASP.NET Core】MVC模型绑定——实现同一个API方法兼容JSON和Form-data输入
- #|88.网络安全渗透测试—[常规漏洞挖掘与利用篇4]—[xss漏洞测试-加载payload的方法]
- 数据库|【分享】—如何学习软件测试
- 《LeetCode算法全集》|LeetCode 146. LRU 缓存
- C++|C++(八股文) —— 指针和引用的区别
- Leetcode|21. 合并两个有序链表
- 【LeetCode热题100道】7. 整数反转