《剑指offer》—— 29. 最小的K个数（Java）

题目描述

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

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
    }
}

思路：

这题乍一看，可以用排序做。确实可以。但是如果数据特别大，大于内存呢？怎么排序？

所以这题虽然可以用排序做出来。但是醉翁之意不在酒啊~ 这题的考点其实是 最大堆 的实现。

不了解最大堆？看下面~

我们了解几个概念：

1.  二叉堆是一种特殊的堆。

2.  二叉堆就结构性质上来说就是一个完全填满的二叉树。
   满足结构性和堆序性。
   结构性：完全二叉树应该满足的树结构；
   堆序性：父节点的键值总是大于或等于（小于或等于）任何 一个子节点的键值，且每个节点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

3.  最大堆：当父节点的键值总是大于或等于任何一个子节点的键值。
   

4. Java中，最大堆可用PriorityQueue实现大顶堆 (优先队列PriorityQueue是Queue接口的实现)。
   PriorityQueue默认是一个小顶堆，然而可以通过传入自定义的Comparator函数来实现大顶堆。
   如下代码实现了一个大顶堆。这里只是简单的传入一个自定义的Comparator函数，就可以实现大顶堆了。

   PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(new Comparator<Integer>() {
           @Override
           public int compare(Integer o1, Integer o2) {                
               return o2 - o1;
           }
       });
   
   
   
   //顺便熟悉一下用 Java 8 中的 Lambda表达式的写法
   PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>((o1,o2), -> o2 - o1);

    

     5. PriorityQueue的几个方法：

add() //添加元素
size() //返回队列元素的个数
poll() //返回并删除队首元素

然后点到为止~更多相关知识，这里就不详细展开了。我们回到题目。

题目说：输入n个整数，找出其中最小的K个数。

1. 那我们可以建立最大堆：maxHeap。
2. 遍历这 n 个数，依次添加进最大堆maxHeap。
   因为maxHeap是最大堆，所以加进来的数会按照最大堆的规则排好，最大的在最上面。
3. 每添加进一个数进 最大堆maxHeap，我们就判断一下最大堆maxHeap中的元素是否大于K个。
4. 若小于K个，则直接添加。
   若大于K个，则将 最大堆maxHeap 堆顶的元素删除，也就是超过K个后，每次都将最大的元素删除。

一句话总结：创建一个最大堆，每次只读入一个数，且只保留最小的 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) {
        if (k > input.length || k <= 0)
            return new ArrayList<>();
   PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {                
            return o2 - o1;
        }
    });
        for (int num : input){
            maxHeap.add(num);
            if(maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }
}


//换成lambda表达式的写法~
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if (k > input.length || k <= 0)
            return new ArrayList<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2) -> o2 - o1); 
        for (int num : input){
            maxHeap.add(num);
            if(maxHeap.size() > k)
                maxHeap.poll();
        }
        return new ArrayList<>(maxHeap);
    }
}

感觉应该讲清楚了~ 有疑问的，欢迎留言~