作者:Yvette-XY | 来源:互联网 | 2023-05-17 07:28
找第k小丑数:用小顶堆每次取顶x,判断set[]是否已有该数x,若无,把x加入set[],并把x*a,x*b,x*c加入堆。第k进入set[]的是第k大丑数。找第k大数:如
找第k小丑数:
用小顶堆每次取顶x,判断set[]是否已有该数x,若无,把x加入set[],并把x*a,x*b,x*c 加入堆。第k进入set[]的是第k大丑数。
找第k大数:
如果所有数字可以用堆装,那么放入大顶堆里面。取到第k个就是了。
否则需要对所有数字分段计数。
给定递增的数组 a[m] 和 b[n],找第k小的a[i] + b[j]:
这等价于从一个特殊的杨氏矩阵Mat[ m ][ n ]中找第k小数, Mat[i][j] = a[i] + b[j],
杨氏矩阵 满足特征 a[i][j] <= a[i+1][j], a[i][j]<= a[i][j+1]
实现方法:
宽搜法(bfs), 每次访问到Mat[i][j]的时候,接下来判断Mat[i][j+1] 和Mat[i+1][j]是否在小顶堆里,如果不在,将其插入到小顶堆。
时间复杂度: O(K*lg K )
#include
#include
#include
#include
#include