K-th Largest Sum from Two Sorted Array

来源：Meetqun, Google

原帖：http://www.meetqun.com/thread-2183-1-1.html

题目：
X+Y 第K大. X =[1,2,3] Y = [2,3,4], S = {x+y| x属于X, y属于Y}, 求S中的第K大数。下面这个链接给了解释。http://blog.csdn.net/shoulinjun/article/details/19179243

思路：X,Y是从大到小排列数组。将X拆分成X[i] + Y[0,...,n-1]的形式。
X[0] + Y[0], X[0] + Y[1], ...X[0] + Y[n-1]
X[1] + Y[0], X[1] + Y[1], ...X[1] + Y[n-1]
X[m-1] + Y[0], X[m-1] + Y[1],...., X[m-1] + Y[n-1]
然后用最大堆来解决问题。

代码:

 struct Pair {   
     int ai,bj;   
     int val;   
     Pair(int i, int j, int v) : ai(i), bj(j), val(v) {}    
 };   
   
 class compare {   
 public:   
     bool operator() (const Pair& a, const Pair& b) {   
         return a.val < b.val;   
     }   
 };   
   
 vector<int> res; // global variable   
 int findKthElement(vector<int>& A, vector& B, int k) {   
     priority_queue<Pair, vector<Pair>, compare> q;   
     for (int i = 0; i < A.size(); ++i) {   
         q.push(Pair(i,0,A[i] + B[0]));   
     }   
     int count = 0;   
     while (!q.empty() && count < k) {   
         int element = q.top().val;    
         int i = q.top().ai, j = q.top().bj;   
         //cout << element << endl;   
         res.push_back(element);   
         q.pop();   
         if (++count == k) return element;   
         if (j < B.size()-1) {   
             q.push(Pair(i,j+1,A[i]+B[j+1]));   
         }   
     }   
     return -1; // not found;   
 }   
   
 int main() {   
     vector<int> A = {6,3,2};   
     vector<int> B = {5,4,1};   
     int k = 9;   
     findKthElement(A,B,k);   
     //for (auto i : res) cout << i << " ";   
     return 0;   
 }