文章目录
题目描述我的分析我的代码大神分析大神代码
题目描述
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。
我的分析
对数组进行排序，从小到大排序，最后输出前k个数就好，用了冒泡排序，时间复杂度太高了，并且没有什么思想，面试要是用我这种肯定被拒
我的代码
import java
.util
.ArrayList
;
public class Solution {
public ArrayList
<Integer> GetLeastNumbers_Solution(int [] input
, int k
) {
ArrayList
<Integer> arrayList
= new ArrayList<>();
if (k
>input
.length
){
return arrayList
;
}
int count
= 0;
for (int i
= 1; i
< input
.length
; i
++) {
for (int j
= 0; j
< input
.length
-1; 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
++) {
arrayList
.add(input
[i
]);
}
return arrayList
;
}
}
大神分析
用最大堆保存这k个数，每次只和堆顶比，如果比堆顶小，删除堆顶，新数入堆。
大神代码
import java
.util
.ArrayList
;
import java
.util
.PriorityQueue
;
import java
.util
.Comparator
;
public class Solution {
public ArrayList
<Integer> GetLeastNumbers_Solution(int[] input
, int k
) {
ArrayList
<Integer> result
= new ArrayList<Integer>();
int length
= input
.length
;
if(k
> length
|| k
== 0){
return result
;
}
PriorityQueue
<Integer> maxHeap
= new PriorityQueue<Integer>(k
, new Comparator<Integer>() {
@Override
public int compare(Integer o1
, Integer o2
) {
return o2
.compareTo(o1
);
}
});
for (int i
= 0; i
< length
; i
++) {
if (maxHeap
.size() != k
) {
maxHeap
.offer(input
[i
]);
} else if (maxHeap
.peek() > input
[i
]) {
Integer temp
= maxHeap
.poll();
temp
= null
;
maxHeap
.offer(input
[i
]);
}
}
for (Integer integer
: maxHeap
) {
result
.add(integer
);
}
return result
;
}
}
