主題
題目連結(jié)：
題目意譯：
你被給定一整數(shù)陣列 nums 以及一正整數(shù) k。你可以從該陣列中選出任意一個(gè)子序列，並將其所有元素加總起來(lái)。
我們定義一個(gè)陣列的「K-總和」為可以獲取（不一定相異）之第 k 大子序列之和。
回傳該陣列的 K-總和。
一個(gè)子序列為一個(gè)可以從另一個(gè)陣列藉由刪除若干個(gè)或零個(gè)元素且不更動(dòng)到剩餘元素的相對(duì)順序而得到的陣列。
注意到空的子序列被視為有著總和值 0。
限制：
n == nums.length
1 ≦ n ≦ 10 ^ 5
-10 ^ 9 ≦ nums[i] ≦ 10 ^ 9
1 ≦ k ≦ min(2000, 2 ^ n)
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [2,4,-2], k = 5
輸出： 2
解釋： 所有我們可能獲得的子序列和為以下，並以降序排序：
- 6 、 4 、 4 、 2 、 2 、 0 、 0 、 -2。
此陣列的 5-總和為 2。
範(fàn)例 2：
輸入： nums = [1,-2,3,4,-10,12], k = 16
輸出： 10
解釋： 此陣列的 16-總和為 10。
解題思維：
首先，第一大的子序列總和的求法很直覺(jué)——把 nums 中所有正數(shù)加總即可得到。
第二大的總和也蠻直覺(jué)的，把 nums 中絕對(duì)值最小者（如果有多個(gè)就隨便取一個(gè)。稱此數(shù)為 x）從第一大總和減去即可。這個(gè)操作對(duì)於 x > 0，即代表原先有挑到 x 現(xiàn)在要把它去除掉；而對(duì)於 x ≦ 0，則代表原本沒(méi)有挑到 x，現(xiàn)在則要包含該數(shù)。
剩下的總和基本上只能動(dòng)態(tài)地比較（例如說(shuō)使用一個(gè)優(yōu)先佇列（Priority Queue）來(lái)找到「下一個(gè)」最大的總和），但是我們每次可以從「現(xiàn)在的」最大總和來(lái)生成下一批更小的總和，其作法類似於上面的方式：
以「現(xiàn)在的」總和是第二大的總和（設(shè)其值為 C）為例，則第三小總和要嘛是 C + |x| - |y| 、要嘛是 C - |y|，其中 y 為 nums 中絕對(duì)值第二小者（因此 |x| ≦ |y|）。
然後我們就重複以上步驟直到找到第 k 大的總和。
而我們可以看到過(guò)程中優(yōu)先佇列中的元素為 O(k) 個(gè)，因此這整個(gè)求第 k 大總和過(guò)程的時(shí)間複雜度為 O(k log k × 「找下一個(gè)最小的絕對(duì)值」)。
而「下一個(gè)最小的絕對(duì)值」可以藉由先把 nums 中的元素複製一份並由它們的絕對(duì)值之大小由小排到大。然後把每個(gè)總和的「x」一同放進(jìn)優(yōu)先佇列之中，便可以知道「下一個(gè)」最小的絕對(duì)值要挑哪一個(gè)。
因此總體的時(shí)間複雜度為 O(n log n) + O(k log k)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
