最小的K个数

方法一

思路分析

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]

复杂度分析

方法二

思路分析

图解

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个数
        
    }
};

复杂度分析

方法三

思路分析

核心代码

# -*- 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#返回排序位置确定的元素下标

空间复杂度