文章
36
粉丝
0
获赞
0
访问
3.7k
算法思想:基于小顶堆的筛选
构建初始小顶堆:首先将数组 M构建成一个小顶堆。在小顶堆中,每个父节点的值都小于或等于其子节点的值,因此堆顶元素(即根节点)就是整个堆中的最小值
提取最小值并调整堆:取出堆顶元素(当前最小值),将其与堆的最后一个元素交换,然后缩小堆的大小(即排除已取出的元素),并对新的堆顶元素进行“下沉”调整,以恢复小顶堆的性质
重复提取:重复上述步骤 10 次,每次都能得到当前堆中的最小值。这 10 个被取出的元素就是数组 M中最小的 10 个数。
过程简述
建堆:将整个数组 M调整成一个小顶堆。
取数:
进行 10 次循环操作。
每次循环中,将堆顶元素 M[0](当前最小值)与堆的最后一个有效元素交换。
减小堆的大小(相当于排除已提取的最小值)。
对新的堆顶元素进行“下沉”操作,以维护小顶堆结构。
结果:最后取出的 10 个元素即为所求。
平均情况下的时间复杂度为O(n),空间复杂度为O(1)
评分及理由
(1)得分及理由(满分5分)
得分:2分
理由:学生使用了小顶堆的方法来解决问题,思路基本正确。但是存在以下问题:
(2)得分及理由(满分5分)
得分:2分
理由:
登录后发布评论
暂无评论,来抢沙发