最小的K个数_

Java

黄小斜

import java.util.TreeSet;

import java.util.ArrayList;

//利用treeset实现红黑树

public class Solution {

public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

ArrayList<Integer>arrayList=new ArrayList<>();

if(input==null || input.length==0 ||k==0 ||k>input.length)return arrayList;

TreeSet<Integer> treeSet=new TreeSet<>();

for(int i=0;i<input.length;i++){

if(treeSet.size()<k){

treeSet.add(input[i]);

}

else {

if(input[i]<treeSet.last()){

treeSet.pollLast();

treeSet.add(input[i]);

}

for(Integer x:treeSet){

arrayList.add(x);

}

return arrayList;

}

发表于 2017-03-23 09:46:54 回复(0)

打工不可能打工的

思路：使用最小堆存储数组中的值，最小堆第一次弹出的值是整个数组最小的值，同时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)

Python3

牛客45854653号

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

wengJJ

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)

C/C++

小红帽__

//冒泡排序的思想，只不过最外层循环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)

Python

XShura

使用大顶堆维护 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)

boypy

构建小顶堆,不用全排列

 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)

drdr

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)

crazychen

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)

Python

苫布碉

方法一：蒂姆排序

# -*- 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)

C/C++

搁浅的鱼儿

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)

Python

L.W.M

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)

Java

召田最帅boy

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)

Java

txy_钟琛

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)

Python 3

deamn

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)

Java

yiyi~

基于快排的优化, 时间复杂度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)

Java

偏北

/**
     * 感谢该文章及其作者 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)

Java

白色黄昏

import java.util.ArrayList;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        process(input, 0, input.length - 1, k);
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            list.add(input[i]);
        }
        return list;
    }
    
    public void process(int[] nums, int L, int R, int k) {
        if (L >= R) {
            return;
        }
        int pivot = nums[L + (int) (Math.random() * (R - L + 1))];
        int[] range = partition(nums, L, R, pivot);
        if (k < range[0]) {
            process(nums, L, range[0] - 1, k);
        } else if (k > range[1]) {
            process(nums, range[1] + 1, R, k);
        } else {
            return;
        }
    }
    
    public int[] partition(int[] nums, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        int cur = L;
        while (cur < more) {
            if (nums[cur] < pivot) {
                swap(nums, cur++, ++less);
            } else if (nums[cur] > pivot) {
                swap(nums, cur, --more);
            } else {
                cur++;
            }
        }
        return new int[]{less + 1, more - 1};
    }
    
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

发表于 2021-10-03 17:17:20 回复(1)

C++

汤姆和佩奇

终于能有一道简单题了哈哈无敌的sort函数真好用！！！

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ans;
                //升序排列 
        sort(input.begin(),input.end());
                //从左向右数k个就OK！
        for(int i=0;i<k;i++){
            ans.push_back(input[i]);
        }
        return ans;
    }
};

发表于 2021-09-30 17:45:21 回复(2)

C++

zcx老bolt

C++ 容器、STL yyds

class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
sort(input.begin(),input.end());
input.resize(k);
return input;
}
};

发表于 2021-09-18 10:07:14 回复(1)

C++

元气少女李逵

class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int>test;
if(k==0) return test ;

int m;

//冒泡排序

for(int i=1;i<=input.size();i++)
{
for(int j=1;j<=input.size()-i;j++)
{
if(input[j]<input[j-1])
{
m=input[j];
input[j]=input[j-1];
input[j-1]=m;
}
}
}
return {input.begin(),input.begin()+k};
}
};

发表于 2021-09-17 09:55:57 回复(0)

最小的K个数

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题