题7

题7

题目

[!question]+
【2022 统考真题】现有 个数保存在一维数组 M 中,需要查找 M 中最小的 10 个数。请回答下列问题。

1. 设计一个完成上述查找任务的算法, 要求平均情况下的比较次数尽可能少, 简述其算法思想 (不需要编程实现)。
2. 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

分析

[!NOTE]+
考虑堆排序-aw实现这个事情，堆排序的核心逻辑是上浮和下沉，我们用数组来实现这个堆的结构
堆排序是一个基于树的结构，那肯定是带着log的时间复杂度，实现排序这个操作需要O(nlogn)的时间复杂度，删除和插入这两个操作，最差需要跑完整个树的高度，对于n个元素来说，高度就是这个级别，时间复杂度是O(logn)
这个题不能按照排序的思想做，每次给数组排序，然后在逐步输出每次排序最小的元素，因为数据量太大了，需要排序的轮数太多了，每次小根堆排序的开销太大
我们选择给这个序列维护成大根堆，每次如果有更小的元素堆顶替换掉，然后下沉堆顶，使得它是标准的大根堆，始终让堆顶以下的元素都是相对小的，和小根堆相比，这里维护大根堆，只用实现下沉这个操作，时间复杂度是O(logn)，最终堆中剩下的元素就是其中最小的十个元素
在这里我们要接触一下随机化的思想：题42

解

[!done]+
题7

1. 算法思想。
   【方法 1】定义含 10 个元素的数组 A ,初始时元素值均为该数组类型能表示的最大数 MAX 。

for (每个元素 s in M) {
    if (s < A[9]) {
        // 丢弃 A[9] 并将 s 按升序插入 A
        // 具体实现省略
    }
}

当数据全部扫描完毕, 数组 A[0] ~ A[9] 保存的就是最小的 10 个数。
【方法 2】定义含 10 个元素的大根堆 H ,元素值均为该堆元素类型能表示的最大数 MAX。

for (每个元素 s in M) {
    if (s < H 的堆顶元素) {
        // 删除堆顶元素并将 s 插入 H
        // 具体实现省略
    }
}

当数据全部扫描完毕, 堆 H 中保存的就是最小的 10 个数。
2) 算法平均情况下的时间复杂度是 O(n) ,空间复杂度是 O(1) 。