题目
找到无序数组中最小的k 个数
java代码
package com.lizhouwei.chapter8;
/**
* @Description: 找到无序数组中最小的k 个数
* @Author: lizhouwei
* @CreateDate: 2018/4/29 7:37
* @Modify by:
* @ModifyDate:
*/
public class Chapter8_4 {
//使用堆排序 时间复杂度为O(logN)
public int[] getKMin(int[] arr, int k) {
if (k > arr.length) {
return new int[]{-1};
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr[i];
headInsert(res, i);
}
for (int i = k; i < arr.length; i++) {
if (arr[i] < res[0]) {
res[0] = arr[i];
heapify(arr, 0, k);
}
}
return res;
}
//堆初始化
public void headInsert(int[] arr, int index) {
int parent = (index - 1) / 2;
while (index > 0) {
if (arr[parent] < arr[index]) {
swap(arr, parent, index);
index = parent;
} else {
break;
}
}
}
//堆排序
public void heapify(int[] arr, int index, int heapSize) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int largest = index;
while (left < heapSize) {
if (arr[left] > arr[index]) {
largest = left;
} else if (right < heapSize && arr[left] > arr[right]) {
largest = right;
} else {
break;
}
swap(arr, largest, index);
index = largest;
left = 2 * index + 1;
right = 2 * index + 2;
}
}
public void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
//测试
public static void main(String[] args) {
Chapter8_4 chapter = new Chapter8_4();
int[] arr = {1, 4, 7, 2, 3, 10, 9, 6, 5, 8};
int[] res = chapter.getKMin(arr, 5);
System.out.print("{1, 4, 7, 2, 3, 10, 9, 6, 5, 8}中前五：");
for (int i = 0; i < res.length; i++) {
System.out.print(res[i]+" ");
}
}
}
结果
