欢聚时代 2019.9.9推荐算法的笔试题 两道基础题

#建堆，可以直接优先队列，不太熟悉python的优先队列库
def heap_step(data,index):
    #index的左右结点不空
    l = index*2+1
    r = index*2+2
    cur = index
    if l<len(data) and data[cur]>data[l]:
        cur=l
    if r<len(data) and data[cur]>data[r]:
        cur=r
    if index!=cur:
        data[index],data[cur]=data[cur],data[index]
        heap_step(data,cur)
    return None     
def mak_heap(data0):
    data = data0[:]
    index_max=len(data)//2
    for index in range(index_max,-1,-1):
        heap_step(data,index)
    return data
def heap_updata_K(data,value):
    #模仿优先队列的插入操作
    if value<=data[0]:
        return
    else:
        data.append(data[0])
        data[0] = value
        data.pop()
        k = len(data)-1
        heap_step(data,0)
#
#data = [1,2,3,4,5,6]
#mak_heap(data)
#
#数据
data_all = [[1,2,3,4,5,6,7,8,9,10,11,12],[2,2,3,0,1,6,0,1,6,0,1,6],[0,1,6,0,1,6,0,1,6,8,7,6]]
#两个列表找最大和topK
#由于是最大的topK，排序记得reverse
def get_he(data1,data2):
    x = sorted(data1,reverse = True)
    y = sorted(data2,reverse = True)
    pri_quequ = mak_heap([i+x[0] for i in y])
    for y_index in range(0,len(y)):
        if y[y_index]+x[0]<=pri_quequ[0]:
            break
            #剪枝，很重要，复杂度立马降下来了
        else:
            for x_index in range(1,len(x)):
                heap_updata_K(pri_quequ,value=y[y_index]+x[x_index])
    return sorted(pri_quequ)
#矩阵找最大行和topK，重复两行的调用就可以了
def get_all_he(data):
    data1 = data[0][:]
    for i in range(1,len(data)):
        data1 = get_he(data1,data[i][:])
    return sorted(data1,reverse=True)
def get_all_min_he(data):
    for i in range(len(data)):
        for j in range(len(data[0])):
            data[i][j]=-data[i][j]
    tmp = get_all_he(data)
    res = [-i for i in tmp]
    #还原回来，虽然没必要
    for i in range(len(data)):
        for j in range(len(data[0])):
            data[i][j]=-data[i][j]
    #
    return res
print(get_all_he(data_all))
print(get_all_min_he(data_all))

[26, 26, 26, 25, 25, 25, 25, 25, 25, 24, 24, 24]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]

tmp = []
for i in range(len(data_all[0])):
    for j in range(len(data_all[1])):
        for k in range(len(data_all[2])):
            tmp.append(data_all[0][i]+data_all[1][j]+data_all[2][k])
tmp.sort()
print(tmp[:len(data_all[0])])
print(tmp[-len(data_all[0]):][::-1])

[1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2]
[26, 26, 26, 25, 25, 25, 25, 25, 25, 24, 24, 24]