但行好事,莫问前程

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

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

实战, 数据结构, 算法, 编程

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

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

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

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

其实源码很简单:

(heap.php) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
<?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的数组,这对于技术人员才是最重要的——要学会思考,要有自己的想法。