给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：
，数组中每个数的大小
要求：空间复杂度 )
，时间复杂度 )
[编程题]最小的K个数
// 使用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)
import java.util.*;
public class Solution {
public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (input == null || input.length <= 0 || input.length < k || k == 0) {
return list;
}
Arrays.sort(input);
for (int i = 0; i < k; i++) {
list.add(input[i]);
}
return list;
}
}
发表于 2022-10-20 11:52:47
回复(0)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if (k == 0 || input == null || input.length == 0) {
return new ArrayList<>();
}
Arrays.sort(input);
List<Integer> array = new ArrayList<>();
for (int i = 0; i < k; i++) {
array.add(input[i]);
}
return (ArrayList<Integer>) array;
}
}
发表于 2022-10-08 15:53:49
回复(0)
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
public ArrayList<Integer> kp(int [] arr,int left,int right,int k){
ArrayList<Integer> list = new ArrayList<>();
int i = left;
int j = right;
int p = arr[left];
while(i<j){
if(arr[j]>=p&&i<j){
j--;
}
if(arr[i]<=p&&i<j){
i++;
}
if(i<j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;}
}
int t = arr[left];
arr[left] = arr[i];
arr[i] = t;
if(i+1==k){
for(int x = 0;x<k;x++){
list.add(arr[x]);
}
return list;
}else if(i+1<k){
return kp(arr, i+1, right,k );
}else{
return kp(arr, left, j-1,k );
}
}
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
int left = 0;
int right = input.length-1;
ArrayList<Integer> list = new ArrayList<>();
if(k==0){
return list;
}else{
list=kp(input, left, right,k );
return list;
}
// ArrayList<Integer> res = new ArrayList<>();
// Arrays.sort(input);
// for (int i = 0; i < k; i++) {
// res.add(input[i]);
// }
// return res;
// }
}
}
最后那个例子出错（但是我看结果一样的啊）
发表于 2022-07-22 13:50:07
回复(0)
问题信息
难度：
352条回答
3173收藏
186513浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
