# -*- coding: utf-8 -*-
# @Time : 2019-08-30 15:56
# @Author : icarusyu
# @FileName: topK_in_sum_of_arr.py.py
# @Software: PyCharm

# 题目
# 有两个大小为N的有序数组a、b(从小到大)，现在需要找出K个最大的数字，
# 其中每个数字是这样构成的(ai+bj)，0<=i，j<N，要求时间空间复杂度尽量低。

# 思路
# 一般topK问题的思路是用堆
# 其实所有的a[i]+b[j]构成一个二维数组，我们不妨将这个二维数组写出来如下：
# -a[0]+b[0]<=a[0]+b[1]<=...<=a[0]+b[n-2]<=a[0]+b[n-1]
# -a[1]+b[0]<=a[1]+b[1]<=...<=a[1]+b[n-2]<=a[1]+b[n-1]
# -...
# -a[n-1]+b[0]<=a[n-1]+b[1]<=...<=a[n-1]+b[n-2]<=a[n-1]+b[n-1]
# 因此想到：
# 构造堆，初始时将最后一列放到堆中对堆初始化，
# 每次从堆弹出一个元素后，从这个元素所在的行取它左边相邻的元素放到堆中，取k次堆顶即为所求

# 复杂度
# 时间复杂度O(klogn)
# 空间复杂度O(n),这个是堆的大小，不需要存二维数组，因为可以设置用于实现堆的数组的数组元素为node
# node中让其包含a[i][j]和位置(i,j),从堆中弹出元素时依据i,j取c[i][j-1]即可

# 参考：https://blog.csdn.net/yl1415/article/details/44874487