给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：
，数组中每个数的大小
要求：空间复杂度 )
，时间复杂度 )
[编程题]最小的K个数
思路：使用最小堆存储数组中的值，最小堆第一次弹出的值是整个数组最小的值，同时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:
//第一种方法：快速选择的方法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)
方法一：蒂姆排序
# -*- 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)
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)
基于快排的优化, 时间复杂度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)
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)
问题信息
难度：
2119条回答
3275收藏
189694浏览
通过挑战的用户
查看代码-
2023-03-13 15:46:59
-
2023-03-09 09:29:58
-
2023-02-26 11:56:24 -
2023-02-25 17:15:38 -
2023-02-23 17:07:36
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
