Article Outline
TOC
Collection Outline
1.题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
2.解析
2.1冒泡排序
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> al = new ArrayList<Integer>();
if(k > input.length){
return al;
}
for(int i = 0; i < k; i++){
for(int j = 0;j<input.length-i-1;j++){
if (input[j] < input[j + 1]) {
int temp = input[j];
input[j] = input[j + 1];
input[j + 1] = temp;
}
}
al.add(input[input.length - i - 1]);
}
return al;
}
}
2.2JAVA类库
import java.util.*;
//时间复杂度为 nlogN
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (input == null || k <= 0 || k > input.length) {
return res;
}
Arrays.sort(input);
for (int i = 0; i < k; i++) {
res.add(input[i]);
}
return res;
}
}
2.3快排的partition函数
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if (input == null || input.length == 0 || input.length < k || k == 0) {
return new ArrayList<>();
}
// 在数组中寻找位置为k - 1的pivot
int start = 0, end = input.length - 1;
int index = partition(input, start, end);
while (index != k - 1) {
if (index < k - 1) {
start = index + 1;
} else {
end = index - 1;
}
index = partition(input, start, end);
}
// 收集这k个数
ArrayList<Integer> res = new ArrayList<>();
for (int i = 0; i <= index; i++) {
res.add(input[i]);
}
return res;
}
public static int partition(int[] arr, int lo, int hi) {
// random swap reduce rate of baddest case appear
swap(arr, lo + (int) Math.random() * (hi - lo + 1), hi);
// divide orginal array to smaller and equal or bigger two part
int small = lo - 1;
while (lo < hi) {
if (arr[lo] < arr[hi]) {
swap(arr, ++small, lo++);
} else {
lo++;
}
}
// put pivot into middle
swap(arr, ++small, hi);
// return middle position
return small;
}
// swap array element in i and j
public static void swap(int[] arr, int i, int j) {
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
2.4最优解
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
if (input == null || input.length == 0 || input.length < k || k == 0) {
return new ArrayList<>();
}
// make a big root heap size of k
// traverse input
// when heap is full and heap's top is bigger than current element
// use current element replace heap's top
PriorityQueue<Integer> bigHeap = new PriorityQueue<>(new MyComparator());
for (int num : input) {
if (bigHeap.size() < k) {
bigHeap.add(num);
} else {
if (num < bigHeap.peek()) {
bigHeap.poll();
bigHeap.add(num);
}
}
}
// collect all k elements
ArrayList<Integer> res = new ArrayList<>();
while (!bigHeap.isEmpty()) {
res.add(bigHeap.poll());
}
return res;
}
// big root heap comparator
class MyComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
}