下面的内容要给大家带来的是，n个整数当中找出当中最小的K个数的Java实现及思路，下面一起和小编来了解一下吧!

题目：

输入n个整数，找到其中最小的K个数。

例：

输入：4,5,1,6,2,7,3,8这8个数字，那么最小的4个数字是1,2,3,4,。

思路1：

用最大堆保存这k个数，每次只和堆顶比，假如比堆顶小，删除堆顶，新数入堆。

代码实现：

import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution
{
    public ArrayList < Integer > GetLeastNumbers_Solution(int[] input, int k)
    {
        ArrayList < Integer > result = new ArrayList < Integer > ();
        int length = input.length;
        if (k > length || k == 0)
        {
            return result;
        }
        PriorityQueue < Integer > maxHeap = new PriorityQueue < Integer > (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])
            {
                Integer temp = maxHeap.poll();
                temp = null;
                maxHeap.offer(input[i]);
            }
        }
        for (Integer integer: maxHeap)
        {
            result.add(integer);
        }
        return result;
    }
}

思路2：

冒泡排序的思想，只不过最外层循环K次就可以了，也就是不用全部排序，只要挑出符合提议的K个即可。

代码实现：

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;
}

思路3：

手写最大堆实现(绝对比PriorityQueue优)

代码实现：

import java.util.ArrayList;
public class Solution
{
    public ArrayList < Integer > GetLeastNumbers_Solution(int[] input, int k)
    {
        ArrayList < Integer > list = new ArrayList < Integer > ();
        // [4,5,1,6,2,7,3,8],0
        if (input == null || k > input.length || k <= 0)
            return list;
        int[] target = new int[k];
        int len = input.length;
        for (int i = 0; i < len; ++i)
        {
            if (i < k)
            {
                target[i] = input[i];
                heapInsertSiftUp(target, i, target[i]);
            }
            else
            {
                if (target[0] > input[i])
                { // 最大堆下沉
                    target[0] = input[i];
                    siftDown(target, 0, target[0]);
                    // 相比优先级队列，这里不会offer操作(里面有上浮)，少了一步上浮调整，效率高了不止一丁点
                }
            }
        }
        for (int i = 0; i < k; ++i)
        {
            list.add(target[i]);
        }
        return list;
    }
    private void heapInsertSiftUp(int[] target, int index, int x)
    {
        while (index > 0)
        {
            int parent = (index - 1) >>> 1;
            if (greater(x, target[parent]))
            {
                target[index] = target[parent]; // 往下拉，避免直接上浮覆盖前面的值
                index = parent;
            }
            else
            {
                break;
            }
        }
        target[index] = x;
    }
    private boolean greater(int i, int j)
    {
        return i > j;
    }
    private void siftDown(int[] target, int k, int x)
    {
        int half = target.length >>> 1;
        while (k < half)
        {
            int child = (k << 1) + 1; // 默认先左孩子
            int big = target[child];
            int right = child + 1;
            if (right < target.length && greater(target[right], big))
            {
                big = target[right];
                child = right; // 可以直接一步big = target[child = right];
            }
            if (greater(x, big)) // x比子节点中的最大值还大，已经是大顶堆了
                break; // 往上拉不动了，准备退出把最初堆顶的结点赋值到上一个结点
            target[k] = big; // 往上拉
            k = child;
        }
        target[k] = x;
    }
}

你的思路是怎样的呢?可以实现吗?想了解更多的Java实例，请继续关注本站了解吧。