給定2個的長度N序列,若從兩個序列各取一個數字則有N*N對,每一數對算兩數之和則有N*N個和。
請求出這N*N個和的第K小
Hint 1: 將兩序列排序
Hint 2: 算法時間複雜度為O(NlgN)或O(NlgNlgN)
Hint 3: 以下舉例
N=3, K=5
序列一: 1 2 3
序列二: 4 5 6
序列一選1相對應的和有(1+4), (1+5), (1+6) 序列A=5,6,7
序列一選2相對應的和有(2+4), (2+5), (2+6) 序列A=6,7,8
序列一選3相對應的和有(3+4), (3+5), (3+6) 序列A=7,8,9
問題可視為從N個長度N的遞增序列總共N*N個數字找出第K小=7
Hint 5(延續Hint 4): 使用Heap記錄所有序列(序列ABC)目前最小的數字是多少,以及這是哪個序列的第幾個數字。
Hint 6(延續Hint 4): 不要將N*N個數字都產生出來,時間與空間都會超過限制
Hint 7: 有別的作法
第一行兩個數字N, K
第二和第三行分別有N個數字代表一序列
0<N<=100,000
0<K<=min(N*N,5N)
0<=序列中數字<=N
第K小的數對和