題目
求最小的k個數(shù)
給定一個數(shù)組，找出其中最小的K個數(shù)下面。例如數(shù)組元素是4,5,1,6,2,7,3,8這8個數(shù)字复颈，則最小的4個數(shù)字是1,2,3,4。如果K>數(shù)組的長度沥割，那么返回一個空的數(shù)組
輸入
[4,5,1,6,2,7,3,8],4
輸出
[1,2,3,4]
分析
這是一個典型的堆應(yīng)用問題耗啦，可以使用大頂堆來解決這個問題
- 拿輸入數(shù)組的前K個數(shù)，來構(gòu)建一個大頂堆
- 遍歷數(shù)組机杜，更新大頂堆
- 堆排序芹彬，輸出有序數(shù)組
源碼
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
if (k == 0 || input == null || k > input.length) {
return new ArrayList<Integer>();
} else {
int[] heap = new int[k + 1];
for (int i = 0; i < k; i++) {
heap[i + 1] = input[i];
}
//初始化大頂堆
heap(k, heap);
//更新大頂堆
for (int i = k; i < input.length; i++) {
if (input[i] < heap[1]) {
heap[1] = input[i];
heapFromTop(1, k, heap);
}
}
System.out.print("heap:");
for (int i = 1; i <= k; i++) {
System.out.print(heap[i] + ",");
}
System.out.println("");
//堆排序
ArrayList<Integer> list = new ArrayList<>();
for (int num = k; num >= 1; num--) {
list.add(0, heap[1]);
heap[1] = heap[num];
heapFromTop(1, num, heap);
}
return list;
}
}
private static void heap(int k, int[] heap) {
for (int i = k / 2; i >= 1; i--) {
int left = i * 2;
int right = i * 2 + 1;
int tempIndex;
if (right > k) {
tempIndex = left;
} else {
tempIndex = heap[left] > heap[right] ? left : right;
}
if (heap[tempIndex] > heap[i]) {
int temp = heap[tempIndex];
heap[tempIndex] = heap[i];
heap[i] = temp;
heapFromTop(tempIndex, k, heap);
}
}
}
private static void heapFromTop(int top, int k, int[] heap) {
for (int l = top; l <= k / 2; l++) {
int left = l * 2;
int right = l * 2 + 1;
int tempIndex;
if (right > k) {
tempIndex = left;
} else {
tempIndex = heap[left] > heap[right] ? left : right;
}
if (heap[tempIndex] > heap[l]) {
int temp = heap[tempIndex];
heap[tempIndex] = heap[l];
heap[l] = temp;
} else {
break;
}
}
}
}
堆的知識
- 堆的定義：堆是一顆每個節(jié)點(diǎn)的左右孩子都小于（小頂堆）或者大于（大頂堆）根節(jié)點(diǎn)的完全二叉樹；
- 堆的存儲：由于是一顆完全二叉樹叉庐，所以適合使用數(shù)組來存儲，一般將堆頂元素存儲在數(shù)組的下標(biāo)為1的位置会喝，這樣第i個節(jié)點(diǎn)的左右孩子的位置就是：i*2陡叠，i*2+1玩郊；最后一顆葉子節(jié)點(diǎn)的位置是：size/2。
- 初始化堆：從最后一顆非葉子節(jié)點(diǎn)開始自底向上堆化枉阵，如果有節(jié)點(diǎn)交換译红，則對子節(jié)點(diǎn)進(jìn)行自頂向下堆化
private static void heap(int k, int[] heap) {
for (int i = k / 2; i >= 1; i--) {
int left = i * 2;
int right = i * 2 + 1;
int tempIndex;
if (right > k) {
tempIndex = left;
} else {
tempIndex = heap[left] > heap[right] ? left : right;
}
if (heap[tempIndex] > heap[i]) {
int temp = heap[tempIndex];
heap[tempIndex] = heap[i];
heap[i] = temp;
heapFromTop(tempIndex, k, heap);
}
}
}
private static void heapFromTop(int top, int k, int[] heap) {
for (int l = top; l <= k / 2; l++) {
int left = l * 2;
int right = l * 2 + 1;
int tempIndex;
if (right > k) {
tempIndex = left;
} else {
tempIndex = heap[left] > heap[right] ? left : right;
}
if (heap[tempIndex] > heap[l]) {
int temp = heap[tempIndex];
heap[tempIndex] = heap[l];
heap[l] = temp;
} else {
break;
}
}
}
- 更新堆：替換堆頂元素，然后自頂向下堆化
heap[1] = input[i];
heapFromTop(1, k, heap);
- 堆排序：堆頂元素有序兴溜，先獲取堆頂元素侦厚，然后用最后一個節(jié)點(diǎn)的元素替換堆頂元素，堆大小-1拙徽，自頂向下堆化刨沦，再次獲取堆頂元素，直到堆中只有一個元素
ArrayList<Integer> list = new ArrayList<>();
for (int num = k; num >= 1; num--) {
list.add(0, heap[1]);
heap[1] = heap[num];
heapFromTop(1, num, heap);
}
