给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：
，数组中每个数的大小
要求：空间复杂度 )
，时间复杂度 )
[编程题]最小的K个数
用priority queue多省事
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// write code here
PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i = 0; i < input.length; i++) {
minheap.offer(input[i]);
}
for (int i = 0; i < k; i++) {
result.add(minheap.poll());
}
return result;
}
}
发表于 2024-09-17 17:47:00
回复(1)
使用快排算法。
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// write code here
quick_sort(input,0,input.length-1);
ArrayList<Integer> arr=new ArrayList<Integer>();
for(int i=0;i<k;i++){
arr.add(input[i]);
}
return arr;
}
void quick_sort(int[]q,int l ,int r){
if(l>=r)return;
int i=l-1,j=r+1,x=q[(l+r)/2];
while(i<j){
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j){
int a=q[i];q[i]=q[j];q[j]=a;
}
}
quick_sort(q,l,j);
quick_sort(q,j+1,r);
}
发表于 2024-09-11 15:20:00
回复(0)
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(k == 0) return list;
for(int i=0;i<input.length;i++){
push(list,input[i],k);
}
return list;
}
public void push(ArrayList<Integer> list,int p,int k){
if(list.size() >= k){
if(p >= list.get(list.size()-1)){
return;
}
list.remove(k-1);
}
int i =0,j=list.size()-1;
while(i<=j){
int m = (i+j)/2;
if(list.get(m) > p){
j = m-1;
}else if(list.get(m) < p){
i = m+1;
}else{
i=m;
break;
}
}
list.add(i,p);
}
发表于 2024-08-30 11:25:15
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// write code here
// 核心思想：采用传统堆，至少能够达到O(NlogN)的时间复杂度
// 至于如何达到O(NlogK)，应当是改进堆，使之仅仅只有K个元素
// 题解中的方法：先把前K个元素建大根堆，然后往后遍历，若小于堆顶元素，则堆顶出堆，新元素入堆
// 遍历结束后，这K个元素就是最小的K个元素
// 0.处理特殊情况
ArrayList<Integer> result = new ArrayList<>();
if (k == 0) {
return result;
}
// 1.创建并初始化大根堆，前K个元素入堆
PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);
for (int i = 0; i < k; i++) {
pq.add(input[i]);
}
// 2.往后遍历数组，尝试用更小的元素替换掉堆中的最大元素
for (int i = k; i < input.length; i++) {
if (input[i] < pq.peek()) {
// 若当前元素小于堆中最大元素，则弹出最大元素，让当前元素入堆顶替
pq.poll();
pq.add(input[i]);
}
}
// 3.此时堆中的k个元素就是所求的k个最小值
while (!pq.isEmpty()) {
result.add(pq.poll());
}
return result;
}
}
发表于 2024-08-29 14:14:31
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
PriorityQueue<Integer> q = new PriorityQueue<>((a,b)->{
return b - a;
});
for (int num : input) {
q.offer(num);
while (q.size() > k) {
q.poll();
}
}
ArrayList<Integer> res = new ArrayList<>();
while (!q.isEmpty()) {
res.add(q.poll());
}
return res;
}
}
发表于 2024-08-07 16:57:01
回复(0)
// 使用java大根堆
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// write code here
if (input == null || input.length == 0 || k <= 0 || k > input.length) {
return new ArrayList<>();
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)-> o2-o1);
int index = 0;
for (; index < k; index++) {
maxHeap.add(input[index]);
}
while(index < input.length) {
if (input[index] < maxHeap.peek()) {
maxHeap.poll();
maxHeap.add(input[index]);
}
index++;
}
return new ArrayList<Integer>(maxHeap);
}
}
发表于 2024-04-26 14:12:26
回复(0)
public class Solution {
/**
* 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数
* 使用优先队列PriorityQueue
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if (input.length < k || k == 0) {
return result;
}
PriorityQueue<Integer> que = new PriorityQueue<>(new MyComparator());
for (int i = 0; i < input.length; i++) {
if (que.size() < k) {
que.offer(input[i]);
continue;
}
if (input[i] < que.peek()) {
que.poll();
que.offer(input[i]);
}
}
while (!que.isEmpty()) {
result.add(que.poll());
}
return result;
}
//PriorityQueue默认从小到大输出，这里自定义比较器让其从大到小输出
class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer i1, Integer i2) {
return i2 - i1;
}
}
}
发表于 2023-10-30 14:56:34
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (k == 0 || input == null || input.length == 0) {
return arrayList;
}
ArrayList<Integer> copy = new ArrayList<>();
for (int i = 0; i < input.length; i++) {
copy.add(input[i]);
}
for (int times = 0; times < k; times++) {
Integer min = copy.get(0);
for (int i = 1; i < copy.size(); i++) {
if (copy.get(i) < min) {
min = copy.get(i);
}
}
copy.remove(min);
arrayList.add(min);
}
return arrayList;
}
}
发表于 2023-10-26 07:29:15
回复(0)
public class Solution {
int size = 0;
int[] arr;
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
arr = new int[input.length + 1];
System.arraycopy(input, 0, arr, 1, input.length);
size = input.length;
// 构建二叉堆，时间复杂度O(n)
for (int i = size / 2; i >= 0; i--) {
percolateDown(i);
}
// 每次删除最小值，时间复杂度O(klogn)
ArrayList<Integer> result = new ArrayList<>();
while (k-- > 0) {
result.add(deleteMin());
}
return result;
}
private int deleteMin() {
int min = arr[1];
arr[1] = arr[size--];
percolateDown(1);
return min;
}
private void percolateDown(Integer hole) {
int tmp = arr[hole];
while (true) {
int child = hole * 2;
if (child > size) {
break;
}
if (child != size && arr[child] > arr[child + 1]) {
child++;
}
if (arr[child] < tmp) {
arr[hole] = arr[child];
hole = child;
} else {
break;
}
}
arr[hole] = tmp;
}
}
发表于 2023-09-23 21:20:15
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param input int整型一维数组
* @param k int整型
* @return int整型ArrayList
*/
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// write code here
ArrayList<Integer> res = new ArrayList<Integer>();
BuildHeap(input);
for (int i = 0; i < k; i++) {
res.add(input[i]);
}
return res;
}
public void adjustHeap(int[] input, int index, int length) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int minmum = index;
if (left < length && input[left] > input[minmum]) {
minmum = left;
}
if (right < length && input[right] > input[minmum]) {
minmum = right;
}
if (minmum != index) {
int temp = input[index];
input[index] = input[minmum];
input[minmum] = temp;
adjustHeap(input, minmum, length);
}
}
public void BuildHeap(int[] input) {
int length = input.length;
int index = length / 2 - 1;
while (index >= 0) {
adjustHeap(input, index, length);
index--;
}
for (int i = length - 1; i > 0; i--) {
int temp = input[0];
input[0] = input[i];
input[i] = temp;
adjustHeap(input, 0, i);
}
}
}
发表于 2023-08-12 21:51:58
回复(0)
public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
// 堆排序，大根堆（堆顶元素为最大值），堆长度为K
//堆顶就是K个数字中的最大值，如果即将进入的元素小于堆顶元素，那就直接替换堆顶元素
//复杂度为log(n)
//将input的前k个元素加入大根堆，然后比较后面的元素和堆顶元素大小，更新堆顶元素
//最后，大顶堆的k个元素就是前k小个元素
ArrayList<Integer> ans=new ArrayList<>();
if(k==0||input.length<=0){
return ans;
}
PriorityQueue<Integer> q=new PriorityQueue<>((o1,o2)->o2.compareTo(o1));//大根堆
for(int i=0;i<k;i++){
q.offer(input[i]);
}
//比较后续元素
for(int i=k;i<input.length;i++){
if(input[i]<q.peek()){
q.poll();
q.offer(input[i]);
}
}
//从堆中取出元素，返回答案
for(int i=0;i<k;i++){
ans.add(q.poll());
}
return ans;
}
发表于 2023-07-21 09:58:09
回复(3)
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(k==0) return list;
//双栈一遍过
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
stack1.add(input[0]);
for(int i=1;i<input.length;i++){
while(!stack1.isEmpty() && input[i]<stack1.peek()){
stack2.add(stack1.pop());
}
if(stack1.isEmpty() || (stack1.peek()<=input[i] && stack1.size()<k))
{
stack1.add(input[i]);
}
while(!stack2.isEmpty() && stack1.size()<k){
stack1.add(stack2.pop());
}
while(!stack2.isEmpty()) stack2.pop();
}
while(!stack1.isEmpty()){
stack2.add(stack1.pop());
}
while(!stack2.isEmpty()){
list.add(stack2.pop());
}
return list;
}
}
发表于 2023-05-11 16:29:39
回复(0)
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;```
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
for (int i = 0; i < input.length; i++) {
res.add(input[i]);
}
Collections.sort(res);
System.out.println(res);
List integers = res.subList(0, k);
return new ArrayList(integers);
}
}
```
public class Solution {
public ArrayList GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList();
for (int i = 0; i < input.length; i++) {
res.add(input[i]);
}
Collections.sort(res);
System.out.println(res);
List integers = res.subList(0, k);
return new ArrayList(integers);
}
}
发表于 2023-05-10 21:29:31
回复(0)
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
return (ArrayList<Integer>) Arrays.stream(input).sorted().limit(k).boxed().collect(Collectors.toList());
}
}
发表于 2023-03-10 17:58:58
回复(0)
一行代码搞定
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
return new ArrayList<Integer>(Arrays.stream(input).sorted().limit(
k).boxed().collect(Collectors.toList()));
}
}
发表于 2022-12-06 12:38:19
回复(1)
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> result = new ArrayList<>();
if(k < 1 || k > input.length) return result;
merge(input, 0, input.length - 1);
for (int i = 0; i < k; i++) result.add(input[i]);
return result;
}
public void merge(int [] input, int left, int right){
if(left >= right) return;
int mid = left + (right - left) / 2;
merge(input, left, mid);
merge(input, mid + 1, right);
int[] tempArr = new int[input.length];
int temL = left,tempR = mid + 1,tempArrIndex = 0;
while (temL <= mid && tempR <= right){
if(input[temL] > input[tempR]){
tempArr[tempArrIndex] = input[tempR];
tempR++;
}else{
tempArr[tempArrIndex] = input[temL];
temL++;
}
tempArrIndex++;
}
while (temL <= mid){
tempArr[tempArrIndex] = input[temL];
temL++;
tempArrIndex++;
}
while (tempR <= right){
tempArr[tempArrIndex] = input[tempR];
tempR++;
tempArrIndex++;
}
tempArrIndex = 0;
for (int i = left; i <= right; i++) {
input[i] = tempArr[tempArrIndex];
tempArrIndex++;
}
}
}
发表于 2022-11-12 10:12:18
回复(0)
topK问题，最小的k个数，可以转换为取相反数最大的K个数。最大数可以联想到大顶堆MaxHeap，java有PriorityQueue的实现
import java.util.ArrayList;
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
for (int num : input) {
maxHeap.add(-num);
}
ArrayList<Integer> results = new ArrayList<Integer>();
while (k > 0 && !maxHeap.isEmpty()) {
results.add(-maxHeap.poll());
k--;
}
return results;
}
}
发表于 2022-10-21 14:21:09
回复(0)
问题信息
难度：
357条回答
3289收藏
190928浏览
通过挑战的用户
查看代码-
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号
