輸入 n 個整數，找出其中最小的 K 個數，例如輸入 4,5,1,6,2,7,3,8 這 8 個數字，則最小的 4 個數字是 1,2,3,4
解題思路
使用任意一種排序演算法即可，得到有序的序列后，就可以直接取出目標值了，但如果遇到海量資料時，如果演算法選擇不當有可能會崩潰，這里推薦兩種比較好的排序演算法，
第一種：改良后的冒泡排序演算法
使用冒泡排序思想，不需要全部遍歷一次，因為題目只要求前 K 個數，所以最外層回圈 K 次就好了，
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(k > input.length) {
return list;
}
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;
}
}
list.add(input[input.length - i - 1]);
}
return list;
}
}
還可以考慮使用堆排序，堆排序的空間復制度僅為 O(1)，并且時間復雜度穩定為 O(nlogN)，適合處理海量資料，對應堆的實作，我們可以使用 Java 為我們提供的優先級佇列 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> list = new ArrayList<>();
int length = input.length;
if(k > length || k <= 0) {
return list;
}
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(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]){
maxHeap.poll();
maxHeap.offer(input[i]);
}
}
for (Integer integer : maxHeap) {
list.add(integer);
}
return list;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/173183.html
標籤：其他
上一篇：Windows下如何查看某個埠被占用，以及如何殺死某個行程
下一篇：任務分配演算法