题解 | #最小的K个数#
最小的K个数
http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
最小的K个数
问题描述：给定一个数组，找出其中最小的K个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
0 <= k <= input.length <= 10000 0 <= input[i] <= 10000
示例1
输入：[4,5,1,6,2,7,3,8],4
返回值：[1,2,3,4]
说明：返回最小的4个数即可，返回[1,3,2,4]也可以
示例2
输入：[1],0
返回值：[]
示例3
输入：[0,1,2,1,2],3
返回值：[0,1,1]
方法一
思路分析
对于本题我们直接想到的是对整个数组进行排序，然后输出数组中的前K个数，因此尝试使用排序算法，而对于0 <= k <= input.length <= 10000的数量级下使用python中sort排序算法是最合适的。蒂姆排序（sort排序）结合使用了归并排序和插入排序，具有良好的性能。此处我们直接使用python中的排序算法。
python核心代码
# -*- coding:utf-8 -*- class Solution: def GetLeastNumbers_Solution(self, tinput, k): # write code here if tinput==None&nbs***bsp;tinput==[]&nbs***bsp;k<0&nbs***bsp;k>len(tinput):#输入的数组为空或者K不符合条件的情况直接返回空 return [] tinput.sort()#对数组进行排序 return tinput[:k]
复杂度分析
- 时间复杂度：蒂姆排序的平均时间复杂度为
- 空间复杂度: 空间复杂度为$O(n)$
方法二
思路分析
对于本题我们能直接想到的求解方法是先将整个数组进行排序，而后输出数组中的前K个数，但是对于较大数组的情况下，排序的时间复杂度会大大增加。因此我们想到先将数组中的前K个数构建大顶堆，此时大顶堆顶点处的值为这K个数里面最大的，而后遍历数组中余下的数，如果第i个数大于大顶堆顶点，则大于全部的K个数，直接跳过，否则，将大顶堆的顶点替换为第i个数，之后将更新后的tmp数组构建大顶堆，直到遍历完整个数组，分析到这里我们也许已经理解为什么开始处构建大顶堆的原因，这样大顶堆始终存储的数组中的最小的K个数。
图解
C++核心代码
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> tmp;
int len =input.size();
if (len <= 0 || len < k || k <= 0 )//如果K大于数组长度返回空
return tmp;
for (int i = 0; i < k; i++)
tmp.push_back(input[i]);//将数组input中的前K个值放入数组tmp
make_heap(tmp.begin(), tmp.end(), less<int>());//K个数构建大顶堆，顶点存储这K个数中最大的
for(int i = k; i < len; i++)//遍历数组中余下的数
{
if (input[i] > tmp.front())//如果第i个数大于大顶堆顶点，则大于这K个数，直接跳过
continue;
else
{
tmp[0]=input[i];//否则，将大顶堆的顶点替换为第i个数
make_heap(tmp.begin(), tmp.end(), less<int>());//更新后的tmp数组构建大顶堆
}
}
sort_heap(tmp.begin(),tmp.end());
return tmp;//大顶堆中的K个数即为input中的最小的K个数
}
}; 复杂度分析
- 时间复杂度：构建一个容量个k的大顶堆时间复杂度为$O(logk)$，共需要更新n-k次，因此总的时间复杂度为$O(nlogk)$
- 空间复杂度: 构建大顶堆借助一个数组，空间复杂度为$O(k)$
方法三
思路分析
本题也可使用快速排序的方法，快速排序算法是一种典型的分治算法，思想非常简单，在待排序的数列中，我们首先要找一个数字作为基准数。一般选择第 1 个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。因为我们要找的只是最小的k个数，并不需要将所有的数都进行排序，只需要在每次排序完，如果基础数的坐标 i 恰好等于 k ,那么我们就可以确定当前前面k个数就是我们的解，这也是减小时间复杂度的一种办法。
核心代码
# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if k > len(tinput) or k <= 0:
return []
start = 0
end = len(tinput) - 1
index = self.quickSort(tinput, start, end)#第一次排序位置确定的元素下标
self.partition(tinput,index,k,start,end)
return tinput[:k]#返回k小的元素
def partition(self,tinput,index,k,start,end):
while index != k-1:#只需要寻找到排序位置确定的元素下标小于k的情况
if index > k-1:#第k小的元素在基准元素左侧
end = index - 1
index = self.quickSort(tinput, start, end)
if index < k-1:#第k小的元素在基准元素右侧
start = index + 1
index = self.quickSort(tinput, start, end)
def quickSort(self, tinput, start, end):#快排
low = start
high = end
temp = tinput[start]#左边第一个元素作为基准元素
while low < high:
while low < high and tinput[high] >= temp:
high -= 1
tinput[low] = tinput[high]
while low <high and tinput[low] < temp:
low += 1
tinput[high] = tinput[low]
tinput[low] = temp#交换元素位置
return low#返回排序位置确定的元素下标
空间复杂度
- 时间复杂度：使用快速排序的时间复杂度为$O(n log n)$，然而我们只需要找到K个最小的数，并不需要将所有的数都进行排序，只需要在每次排序完，如果基础数的坐标 $i$恰好等于 $k$ ,那么我们就可以确定当前前面K个数就是我们的解，这K个数是无序的，每一次只处理一侧的数据，而temp = tinput[start]取左边第一个元素作为基准元素，最坏的时间复杂度仍是$O(n^2)$
- 空间复杂度：不需要额外的空间，空间复杂度为$O(1)$
查看5道真题和解析