首页 > 试题广场 >

最小的K个数

[编程题]最小的K个数
  • 热度指数:1194479 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的可能有重复值的数组,找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围:,数组中每个数的大小
要求:空间复杂度 ,时间复杂度 O(nlogk)

示例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]
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> output;
        int a=input.size();
        if(a<1||k<1||k>a)
            return output;
        int temp;
        for(int i=1;i<=k;++i){
            for(int j=a-1;j>0;--j){
                if(input[j]<input[j-1])
                {temp=input[j-1];
                input[j-1]=input[j];
                input[j]=temp;}
            }
        }
        for(int m=0;m<k;++m){
            output.push_back(input[m]);
        }
        return output;
    }
};
 //利用最简单的冒泡排序,但是不需要全部按照从小到大排,只需要排k次即可。
//因为没想到vector还有最简单的sort函数,所以就笨方法了。

编辑于 2019-10-18 20:37:40 回复(0)
更多回答
//堆排序,复杂度是o(nlogn),比较稳定适合大数据量的排序,如果是快排的话分的不均匀容易引起
//复杂度是o(n^2),快排的话大数据量容易引起OOM
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        if(input==null||input.length==0||input.length<k){
            return result;
        }
        //构建大顶堆
        for(int i=k/2-1;i>=0;i--){
            adjustHeap(input,i,k-1);
        }
        //我们前k个元素的大顶堆已经构建好了,剩下的就是其余的和大顶堆的最大值比较了
        for(int i=k;i<input.length;i++){
            if(input[i]<input[0]){
                int temp=input[i];
                input[i]=input[0];
                input[0]=temp;
                adjustHeap(input,0,k-1);
                
            }
        }
        //我们将调整好的前k个数放进链表里面
        for(int i=0;i<k;i++){
            result.add(input[i]);
        }
        return result;
        
        
    }
            
            //构建大顶堆
    public  void adjustHeap(int[] input,int i,int k){
        //先把最上面根节点保存了
        int temp=input[i];
        for(int j=i*2+1;j<=k;j=j*2+1){
            //j可以等于k,但是下面的程序不能,我们还要判断j和j+1呢
            if(j<k&&input[j]<input[j+1]){
                j++;
            }
            if(temp>input[j]){
                break;
            }
            input[i]=input[j];
            i=j;
        }
        input[i]=temp;
    }
}

发表于 2017-01-06 19:36:21 回复(4)
思路:使用最小堆存储数组中的值,最小堆第一次弹出的值是整个数组最小的值,同时k- -,然后最小堆会自动调整堆内的数的顺序以保持最小堆的性质不变...一直下去直到k的值变成0,之前所有弹出的数进入ArrayList
      最小堆的实现,使用PriorityQueue优先级队列,重写比较器
import java.util.PriorityQueue;
import java.util.ArrayList;
import java.util.Comparator;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (k > input.length) {
            return res;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new MyComparator());
        for (int i = 0; i < input.length; i++) {
            queue.add(input[i]);
        } 
        while (k>0) {
            res.add(queue.poll());
            k--;
        }
        return res;
    }
    
    public class MyComparator implements Comparator<Integer> {
        @Override
        public int compare(Integer o1, Integer o2) {
            // TODO Auto-generated method stub
            return o1 - o2;
        }
    }
}

发表于 2018-07-20 23:51:32 回复(4)
一个非常好的思路,就是利用简单选择排序,向量初始为一个无序区,每次从无序区中选出一个最小元素与无序区的第一个元素交换,并将其输出,这样经过k趟排序,就能得到最小的k个数了,代码如下:
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.size()==0 || k<=0 || k>input.size()) 
            return res;
        //i用来循环k次,j用来从无序区中遍历元素,index标记最小元素的下标
       	int i=0,j=0,index=0;
        for(i;i<k;i++) {
            index=i;
            for(j=i+1;j<input.size();++j) 
                if(input[j]<input[index]) index=j;
            res.push_back(input[index]);
            if(index!=i)
          		swap(input[i],input[index]);
            
        }
        return res;
    }
};

发表于 2016-03-25 23:30:43 回复(1)
class Solution:
    def quicksort(self,nums):
        if len(nums)<2:
            return nums
        else:
            flag=nums[0]
            less=[i for i in nums[1:] if i <flag]
            more=[i for i in nums[1:] if i>= flag]
            return self.quicksort(less)+[flag]+self.quicksort(more)
    def GetLeastNumbers_Solution(self, tinput, k):
        if k>len(tinput):
            return []
        else:
            alist=self.quicksort(tinput)
            return alist[:k]

发表于 2021-08-24 15:51:40 回复(0)
Python
两种思路:
先排序后取值
进行k次取最小值的操作(k次选择排序)
# -*- coding:utf-8 -*-
class Solution:
    def quickSort(self,nums):
        if not nums:
            return []
        mid = nums[0]
        left = self.quickSort([x for x in nums[1:] if x<mid])
        right = self.quickSort([x for x in nums[1:] if x>=mid])
        return left+[mid]+right
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
#         先排序再取值
        if k>len(tinput):
            return []
        result = self.quickSort(tinput)
        return result[:k]
#         k次选择排序
#         if k>len(tinput):
#             return []
#         res = []
#         for _ in range(k):
#             Min = tinput[0]
#             for num in tinput:
#                 if num < Min:
#                     Min = num
#             res.append(Min)
#             tinput.remove(Min)
#         return res


发表于 2021-04-30 16:10:48 回复(0)
//冒泡排序的思想,只不过最外层循环K次就可以了,也就是说不用全部排序,只挑出符合提议的K个就可以。
/*class Solution {
public:
    
    vector<int> vec;
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
   
        if(input.size()<k) return vec;
        
        for(int i=0;i<k;++i)
        {
            for(int j=0;j<input.size()-1-i;++j)
            {
                if(input[j]<input[j+1])
                {
                    int t=input[j];
                    input[j]=input[j+1];
                    input[j+1]=t;
                }
            }
            vec.push_back(input[input.size()-1-i]);
        }
        return vec;
    }
};*/
//求最小的k个数,用最大堆
class Solution {
public:
    
    vector<int> vec;
    void heapSort(vector<int>& input,int root ,int len)
    {
        for(int j=len-1;j>=root;--j)
        {
            int parent=(j+root-1)/2;
            if(input[parent]>input[j])
            {
                int t=input[parent];
                input[parent]=input[j];
                input[j]=t;
            }
        }
    }
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        if(input.size()<k) return vec;
        for(int i=0;i<k;++i)
        {
             heapSort(input,i,input.size());
             vec.push_back(input[i]);
        }
       return vec;
    }
};

发表于 2019-08-23 23:23:34 回复(0)
使用大顶堆维护 k 大小的大顶堆每次小于堆顶元素就将删除堆顶元素将新元素放进去重新调整。使用了heapq的内置数据结构,用了一个trick 因为默认是创建小顶堆,所以在添加元素的时候加个 负号就变成大顶堆了。
import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if k > len(tinput) or k == 0: return []
        heap = []
        for num in tinput:
            if len(heap) < k:
                heapq.heappush(heap, -num)
            else:
                if -num > heap[0]:
                    heapq.heapreplace(heap, -num)
        return sorted(list(map(lambda x: x*-1, heap)))

python  nlog(n)内置sorted函数 精简版
# python精简版
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if not tinput or k > len(tinput): return []
        return sorted(tinput)[:k]



编辑于 2018-09-17 15:45:05 回复(0)
构建小顶堆,不用全排列

 void HeapAdjust(vector<int>&vec,int s,int high)
    {
        int temp=vec[s];
        for(int i=2*s+1;i<=high;i=2*i+1)
        {
            if((i<high)&&vec[i]>vec[i+1])
                i++;
            if(temp<vec[i])
                break;
            vec[s]=vec[i];
            s=i;
        }
        vec[s]=temp;
    }
    
    void HeapSort(vector<int>& vec,int k)
    {
        int high=vec.size()-1;
        for(int i=(high+1)/2-1;i>=0;i--)
            HeapAdjust(vec,i,high);
        int temp;
        for(int i=high;i>0;i--)
        {
            temp=vec[0];
            vec[0]=vec[i];
            vec[i]=temp;
            if(i==high+1-k)
                break;
            HeapAdjust(vec,0,i-1);
        }
    }
    
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> output;
        if(input.size()<k)
            return output;
        HeapSort(input,k);
        for(int i=0;i<k;i++)
            output.push_back(input[input.size()-1-i]);
        return output;
        
    }
发表于 2017-11-05 16:17:44 回复(0)
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> result;

        // 检查k是否合法
        if(k<=0 || k > input.size())
            return result;

        //预先分配存放结果的数组,多分了一个元素的空间
        result.reserve(k+1);
        for(int i=0; i<k+1; i++){
            result.push_back(input[i]);
           }

        // 建堆
        make_heap(result.begin(), result.end()-1);

        for(int i=k; i< input.size(); ++i){
            // 如果第k个元素比堆的最大元还小,就将该元素插入数组中的最后一个位置,也就是result[k]
            if(input[i] < result[0]){
                result[k] = input[i];
                pop_heap(result.begin(), result.end()); // 删除对顶元素时,result[k]会作为临时的堆顶然后下滤
            }

        }

        // 将多余的空间删除并返回结果
        result.erase(result.end()-1);
        sort(result.begin(), result.end());

        return result;
    }
};
发表于 2017-09-19 20:10:12 回复(0)
class Solution {
public:
    //第一种方法:快速选择的方法O(n)
	vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
		vector<int> ret;
        if(k > input.size()) return ret;
		int s = 0, e = input.size() - 1;
		int index = -1;
		while (index != k-1) {
			if (index > k - 1) e = index - 1; //因为index>k-1的,所以再递归的时候,e是等于index-1的
			else s = index + 1;
			index = partition(input, s, e);//不断的迭代,使得当前的index=k-1;
		}
		for (int i = 0; i < k; ++i)
			ret.push_back(input[i]);
		return ret;
	}
private:
	int partition(vector<int> &input, int s, int e){
		int j = s-1;
		int cmp = input[e];
		for (int i = s; i < e; ++i) {
			if (input[i] < cmp)
				swap(input[i], input[++j]);
		}
		swap(input[e], input[++j]);
		return j;
	}	
    //第二种方法:使用multiset,时间复杂度为O(nlogk),适合处理海量数据
    /*typedef multiset<int, greater<int> > intSet;
    typedef multiset<int, greater<int> >::iterator set_it;
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k){
        if(k > input.size()) return vector<int>();
        intSet leastKNum;
        vector<int>::iterator it1 = input.begin(); 
        for( ; it1 != input.end(); ++it1){
            if(leastKNum.size() < k)
                leastKNum.insert(*it1);
            else{
                set_it it2 = leastKNum.begin();
                if(*it2 > *it1){
                    leastKNum.erase(it2);
                    leastKNum.insert(*it1);
                }
            }
        }
        vector<int> ret(leastKNum.begin(), leastKNum.end());
        return ret;       
    }*/
};

发表于 2017-05-20 18:31:20 回复(2)
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if(input.length==0) return arr; 
        if(input.length<k) return arr;
        int low = 0;
        int high = input.length-1;        
        int index = partition(input, 0, high);
        
        while(index!=k-1){
            if(index<k-1){                
                index = partition(input, index+1, high);                
            }else{
                index = partition(input, low, index-1);
            }
        }
        for(int i=0;i<k;i++){
            arr.add(input[i]);
        }   
        return arr;
    }        
    
    public int partition(int [] array,int low,int high){
        int temp = array[low];
        while(low<high){
            while(low<high && array[high]>=temp){
                high--;
            }
            array[low] = array[high];
            while(low<high && array[low]<=temp){
                low++;
            }
            array[high] = array[low];
        }
        array[low] = temp;
        return low;
    }
}

发表于 2015-04-12 00:47:10 回复(1)
哈哈,我是来闹着玩的
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> a=new ArrayList<>();
        if(input==null || k>input.length) return a;
        Arrays.sort(input);
        for(int i=0; i<k; i++)
            a.add(input[i]);
        return a;
    }
}
冒泡排序
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> a=new ArrayList<>();
        if(input==null || k>input.length) return a;
        for(int i=1; i<input.length; i++){
            for(int j=0; j<input.length-i; j++){
                if(input[j]>input[j+1]){
                    int temp=input[j];
                    input[j]=input[j+1];
                    input[j+1]=temp;
                }
            }
        }
        for(int i=0; i<k; i++)
            a.add(input[i]);
        return a;
    }
}



//选择排序
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> a=new ArrayList<>();
        if(input==null || k>input.length) return a;
        for(int i=0; i<input.length-1; i++){
            for(int j=i+1; j<input.length; j++){
                if(input[i]>input[j]){
                    int temp=input[i];
                    input[i]=input[j];
                    input[j]=temp;
                }
            }
        }
        for(int i=0; i<k; i++)
            a.add(input[i]);
        return a;
    }
}
快速排序

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr=new ArrayList<>();
        if(input.length<k||input.length==0) return arr;
        sort(input,0,input.length-1);
        for(int i=0; i<k; i++)
            arr.add(input[i]);
        return arr;
    }
     public void sort(int[] a, int left, int right){
        if(left<right){
            int mid=isMid(a,left,right);
            sort(a,left,mid-1);
            sort(a,mid+1,right);
        }
    }
    public int isMid(int[] a,int left, int right){
        int mid=a[left];
        while(left<right){
            while(a[right]>=mid && left<right)
                right--;
            a[left]=a[right];
            while(a[left]<=mid && left<right)
                left++;
            a[right]=a[left];
        }
        a[left]=mid;
        return left;
    }
}

归并排序
import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> arr=new ArrayList<>();
        if(input.length<k||input.length==0) return arr;
        sort(input,0,input.length-1);
        for(int i=0; i<k; i++)
            arr.add(input[i]);
        return arr;
    }
     public void sort(int[] a, int left, int right){
        if(left<right){
            int mid=(left+right)/2;
            sort(a,left,mid-1);
            sort(a,mid+1,right);
            mergeSort(a,left,mid,right);
        }
    }
    public void mergeSort(int[] a,int left, int mid, int right){
        int[] b=new int[right+1];
        int index=left;
        int t=left;
        int ri=mid+1;
        while(left<=mid && ri<=right){
            b[index++]=(a[left]<a[ri])? a[left++]:a[ri++];
        }
        while(left<=mid)
            b[index++]=a[left++];
        while(ri<=right)
            b[index++]=a[ri++];
        for(int i=t; i<=right; i++)
            a[i]=b[i];
    }
}

编辑于 2018-07-30 09:46:22 回复(0)
方法一:蒂姆排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if tinput == [] or k > len(tinput):
            return []
        tinput.sort()
        return tinput[: k]
方法二:快速排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def quick_sort(lst):
            if not lst:
                return []
            pivot = lst[0]
            left = quick_sort([x for x in lst[1: ] if x < pivot])
            right = quick_sort([x for x in lst[1: ] if x >= pivot])
            return left + [pivot] + right

        if tinput == [] or k > len(tinput):
            return []
        tinput = quick_sort(tinput)
        return tinput[: k]
方法三:归并排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def merge_sort(lst):
            if len(lst) <= 1:
                return lst
            mid = len(lst) // 2
            left = merge_sort(lst[: mid])
            right = merge_sort(lst[mid:])
            return merge(left, right)
        def merge(left, right):
            l, r, res = 0, 0, []
            while l < len(left) and r < len(right):
                if left[l] <= right[r]:
                    res.append(left[l])
                    l += 1
                else:
                    res.append(right[r])
                    r += 1
            res += left[l:]
            res += right[r:]
            return res
        if tinput == [] or k > len(tinput):
            return []
        tinput = merge_sort(tinput)
        return tinput[: k]
方法四:堆排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def siftup(lst, temp, begin, end):
            if lst == []:
                return []
            i, j = begin, begin * 2 + 1
            while j < end:
                if j + 1 < end and lst[j + 1] > lst[j]:
                    j += 1
                elif temp > lst[j]:
                    break
                else:
                    lst[i] = lst[j]
                    i, j = j, 2 * j + 1
            lst[i] = temp

        def heap_sort(lst):
            if lst == []:
                return []
            end = len(lst)
            for i in range((end // 2) - 1, -1, -1):
                siftup(lst, lst[i], i, end)
            for i in range(end - 1, 0, -1):
                temp = lst[i]
                lst[i] = lst[0]
                siftup(lst, temp, 0, i)
            return lst

        if tinput == [] or k > len(tinput):
            return []
        tinput = heap_sort(tinput)
        return tinput[: k]
方法五:冒泡排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def bubble_sort(lst):
            if lst == []:
                return []
            for i in range(len(lst)):
                for j in range(1, len(lst) - i):
                    if lst[j-1] > lst[j]:
                        lst[j-1], lst[j] = lst[j], lst[j-1]
            return lst

        if tinput == [] or k > len(tinput):
            return []
        tinput = bubble_sort(tinput)
        return tinput[: k]
方法六:直接选择排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def select_sort(lst):
            if lst == []:
                return []
            for i in range(len(lst)-1):
                smallest = i
                for j in range(i, len(lst)):
                    if lst[j] < lst[smallest]:
                        smallest = j
                lst[i], lst[smallest] = lst[smallest], lst[i]

            return lst

        if tinput == [] or k > len(tinput):
            return []
        tinput = select_sort(tinput)
        return tinput[: k]
方法七:插入排序
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        def Insert_sort(lst):
            if lst == []:
                return []
            for i in range(1, len(lst)):
                temp = lst[i]
                j = i
                while j > 0 and temp < lst[j - 1]:
                    lst[j] = lst[j - 1]
                    j -= 1
                lst[j] = temp
            return lst

        if tinput == [] or k > len(tinput):
            return []
        tinput = Insert_sort(tinput)
        return tinput[: k]

发表于 2017-07-24 11:50:16 回复(40)
1、全排序  时间复杂度O(nlogn)  *通过牛客*

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.empty()||k>input.size()) return res;
        
        sort(input.begin(),input.end());
        
        for(int i=0;i<k;i++)
            res.push_back(input[i]);
        
        return res;
        
    }
};
2、Partiton思想 时间复杂度O(n)   *通过VS2013,牛客超时,很纳闷,欢迎找错*

class Solution {
public:
    int Partition(vector<int>& input, int begin, int end)
    {
    	int low=begin;
        int high=end;
        
        int pivot=input[low];
        while(low<high)
        {
            while(low<high&&pivot<=input[high])
                high--;
            input[low]=input[high];
            while(low<high&&pivot>=input[low])
                low++;
            input[high]=input[low];
        }
        input[low]=pivot;
        return low;
    }
    
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        
        int len=input.size();
        if(len==0||k>len) return vector<int>();
        if(len==k) return input;
        
        int start=0;
        int end=len-1;
        int index=Partition(input,start,end);
        while(index!=(k-1))
        {
            if(index>k-1)
            {
                end=index-1;
                index=Partition(input,start,end);
            }
            else
            {
                start=index+1;
                index=Partition(input,start,end);
            }
        }
        
        vector<int> res(input.begin(), input.begin() + k);
        
        return res;
    }

};
3、最大堆 时间复杂度O(nlogk)  *通过VS2013,牛客超时,很纳闷,欢迎找错*
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { 
        int len=input.size();
        if(len<=0||k>len) return vector<int>();
        
        vector<int> res(input.begin(),input.begin()+k);
        //建堆
        make_heap(res.begin(),res.end());
        
        for(int i=k;i<len;i++)
        {
            if(input[i]<res[0])
            {
                //先pop,然后在容器中删除
                pop_heap(res.begin(),res.end());
                res.pop_back();
                //先在容器中加入,再push
                res.push_back(input[i]);
                push_heap(res.begin(),res.end());
            }
        }
        //使其从小到大输出
        sort_heap(res.begin(),res.end());
        
        return res;
        
    }
};
4、红黑树:multiset集合  利用仿函数改变排序顺序 时间复杂度O(nlogk)  *通过牛客*
class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len=input.size();
        if(len<=0||k>len) return vector<int>();
        
        //仿函数中的greater<T>模板,从大到小排序
        multiset<int, greater<int> > leastNums;
        vector<int>::iterator vec_it=input.begin();
        for(;vec_it!=input.end();vec_it++)
        {
            //将前k个元素插入集合
            if(leastNums.size()<k)
                leastNums.insert(*vec_it);
            else
            {
                //第一个元素是最大值
                multiset<int, greater<int> >::iterator greatest_it=leastNums.begin();
                //如果后续元素<第一个元素,删除第一个,加入当前元素
                if(*vec_it<*(leastNums.begin()))
                {
                    leastNums.erase(greatest_it);
                    leastNums.insert(*vec_it);
                }
            }
        }
        
        return vector<int>(leastNums.begin(),leastNums.end()); 
    }
};

编辑于 2016-07-28 09:54:57 回复(87)
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        tinput.sort()
        if k>len(tinput): return []
        return tinput[:k]

发表于 2017-10-05 15:02:11 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        Arrays.sort(input);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i <= k - 1; i++) {
            list.add(input[i]);
        }
        return list;
    }
}

发表于 2022-07-10 22:11:02 回复(0)
import java.util.*;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });

        for (int i = 0; i < input.length; i++) {
            queue.add(input[i]);
        }

        ArrayList<Integer> list = new ArrayList<>();
        while (k > 0) {
            list.add(queue.poll());
            k--;
        }
        return list;
    }
}

发表于 2022-05-27 12:36:06 回复(0)
import heapq
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        return heapq.nsmallest(k,input)
发表于 2022-05-01 14:24:35 回复(0)
基于快排的优化, 时间复杂度O(2n)
import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k <= 0) {
            return new ArrayList<>();
        }
        return helper(input, 0, input.length - 1, k);
    }
    
    public ArrayList<Integer> helper(int[] input, int start, int end, int k) {
        int i = start, j = end;
        int target = input[start];
        while (i < j) {
            while (i < j && input[j] >= target) {
                j--;
            }
            while (i < j && input[i] <= target) {
                i++;
            }
            if (i < j) {
                int temp = input[j];
                input[j] = input[i];
                input[i] = temp;
            }
        }
        input[start] = input[i];
        input[i] = target;
        if (i - start + 1 <= k) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int index = start; index <= i; index++) {
                list.add(input[index]);
            }
            if (i - start + 1 < k) {
                list.addAll(helper(input, i + 1, end, k - i + start - 1));
            }
            return list;
        } else {
            return helper(input, start, i, k);
        }
    }
}


发表于 2022-02-15 21:27:20 回复(0)
/**
     * 感谢该文章及其作者 https://www.cnblogs.com/chengxiao/p/6129630.html
     * @param input
     * @param k
     * @return
     */
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<Integer>();

        if (input == null || input.length <= 0 || k <= 0) {
            return list;
        }

        // 先对前k个数,构造成大顶堆
        for (int i = k / 2 - 1; i >= 0; i--) {
            adjustHeap(input, i, k);
        }

        // 针对k个数后面的数,依次比对是否比大顶堆的根元素小,如果小的话,则进行交换,并重新调整堆
        for (int i = k; i < input.length; i++) {
            if (input[i] >= input[0]) {
                continue;
            }
            int tmp = input[i];
            input[i] = input[0];
            input[0] = tmp;
            adjustHeap(input, 0, k);
        }

        for(int j = 0; j<k; j++) {
            list.add(input[j]);
        }

        return list;
    }
    
    /**
     * 构造及调整堆
     * @param input
     * @param i
     * @param length
     */
    private void adjustHeap(int[] input, int i, int length) {
        int tmp = input[i];//先取出当前元素i
        for (int m = i * 2 + 1; m < length; m = m * 2 + 1) {//从i结点的左子结点开始,也就是2i+1处开始
            if (m + 1 < length && input[m] < input[m + 1]) {//如果左子结点小于右子结点,m指向右子结点
                m = m + 1;
            }
            if (input[m] > tmp) {//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                input[i] = input[m];
                i = m;
            } else {
                break;
            }
        }
        input[i] = tmp;//将temp值放到最终的位置
    }


发表于 2021-12-16 00:07:15 回复(0)