趣味题：找出N个数字中最大的K个

算是一个面试题吧，内容就是如标题所写的一样：

给定N个指定的数字，输出前K个最大的数字，比如给出了1，2，3，4，5，6，7，8，要求输出前3个最大的数字，那么就输出8，7，6

其实这个题目，看起来很简单，其实只需要从大到小排序之后，输出前K个数字就可以了，只是排序有很多种算法——常用的就有冒泡排序、选择排序、插入排序、归并排序、快速排序等等，冒泡、选择、插入的时间复杂度是O(n²)，归并、快速的时间复杂度是O(n*lgn)。如果需要自己手动实现排序算法的话，那么使用快速排序和归并排序的效果肯定是最好的。

不过这道题里，我选择了PHP中自带的数据结构 SplMaxHeap 来完成这个问题，也就是用了堆排序。

其实源码很简单：

(heap.php) download

<?php
/**
 * Created by PhpStorm.
 * User: caiknife
 * Date: 2018/11/17
 * Time: 14:54
 */

namespace App\Cron;


class Number
{
    public function main()
    {
        $this->printKMaxFromN(10, 3);
    }

    public function printKMaxFromN($n = 1, $k = 1)
    {
        if ($n <= 0 || $k <= 0) {
            echo "BOTH n k must be positive." . PHP_EOL;
            exit();
        }

        if ($n < $k) {
            echo "n MUST geq k." . PHP_EOL;
            exit();
        }

        $tmpHeap = new \SplMaxHeap();

        for ($i = 0; $i < $n; $i++) {
            $tmpHeap->insert(rand(0, 50));
        }

        for ($i = 0; $i < $k; $i++) {
            echo $tmpHeap->current() . PHP_EOL;
            $tmpHeap->next();
        }
    }
}

上面的代码就是给定了10个0到50的随机数，每生成一个就放入到SplMaxHeap中。

堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

总结

在找出前K个最小(或最大)的元素时，如果元素个数较少，可以采用简单选择排序；如果元素较多，可以采用堆排序；如果元素基本有序，可以采用冒泡排序。本文采用的是堆排序，时间复杂度是O(n*lgk)。

虽然PHP的数组几乎是万能的，但是也别忘了PHP还是提供了更多更强大的数据结构可以让我们使用，在特定的场景下使用合适的数据结构，不要一股脑儿地只使用PHP的数组，这对于技术人员才是最重要的——要学会思考，要有自己的想法。

CDEFGAB 1010110

挖了太多坑，一点点填回来

趣味题：找出N个数字中最大的K个