最小的k个数

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

分析

堆排序。小根堆。

代码:

import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if (input.length < k) return list;
int len = input.length;
for (int i = (len - 2) / 2; i >= 0; i--) {
adjustHeap(input, i, len - 1);
}
for (int i = len - 1; i > len - 1 - k; i--) {
list.add(input[0]);
input[0] = input[i];
adjustHeap(input, 0, i-1);
}
return list;
}
public static void adjustHeap(int[] a, int head, int tail) {
int i = head;
for (int j = 2*i + 1; j < tail; j = 2*i + 1) {
if (a[j+1] < a[j]) j++;
if (a[i] <= a[j]) break;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
}
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :