leetcode面试题9 前k大的和
初阶：有两个数组A和B，每个数组有k个数，从两个数组中各取一个数加起来可以组成k*k个和，求这些和中的前k大。
进阶：有N个数组，每个数组有k个数，从N个数组中各取一个数加起来可以组成k^N个和，求这些和中的前k大。
解答
初阶：定义C[i][j] = A[i]+B[j]，假设A,B从大到小排序，那么C[0][0]为最大的和。
将A和B的和变为一个矩阵，更容易思考。
将C[0][0]拿走以后，C[1][0]和C[0][1]则都可能成为第二个最大和。设定可能成为最大和的集合S，一开始S={C[0][0]}，每次从集合中选一个最大的数C[i][j]出来，然后将C[i+1][j]和C[i][j+1]加入到集合中（如果有的话）。直到选足k个数。由于同时可能在集合中存在的元素只有n个（每行每列会同时有一个数在集合中），采用堆来实现该集合，每次找一个最大数复杂度O(logn)，总时间复杂度O(nlogn)
进阶：先对前两个数组求前k大和，将结果与第三个数组求前k大和，然后第四个……直到第N个。
面试官角度：
初阶问题的难度是需要将所有的和构造成一个矩阵的形式来思考。然后考察基本的数据结构堆的使用。 进阶问题中，考察的是如何将一个复杂的问题化简为一个我们已经知道解法的问题。我们可以解决2个数组求前k大和的问题了，那么N个数组的情况，就想办法变为2个数组的情况就可解了。
https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.01.md
1、谷歌面试题：输入是两个整数数组，他们任意两个数的和又可以组成一个数组，求这个和中前k个数怎么做？
分析：
“假设两个整数数组为A和B，各有N个元素，任意两个数的和组成的数组C有N^2个元素。
那么可以把这些和看成N个有序数列：
A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…
…
A[N]+B[1] <= A[N]+B[2] <= A[N]+B[3] <=…
问题转变成，在这N^2个有序数列里，找到前k小的元素”
2、有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk)，A和B都按升序排列。对于1<=i,j<=k，求k个最小的（ai+bj）。要求算法尽量高效。
3、给定一个数列a1,a2,a3,...,an和m个三元组表示的查询，对于每个查询(i，j，k)，输出ai，ai+1，...，aj的升序排列中第k个数。
Read full article from leetcode面试题9 前k大的和