100個(gè)數(shù)組的數(shù)組元素合成一個(gè)10000個(gè)數(shù)的數(shù)組，然后按值遞增排序，取前100個(gè)，這個(gè)運(yùn)算次數(shù)是 10000 * 10000 = 一億？有說要考慮性能啥的嗎？

還有個(gè)思路就是每次都取數(shù)組的第一個(gè)元素來比較，找最小的，然后取出，再從所在的數(shù)組剔除這個(gè)(第一個(gè))元素，然后再取每個(gè)數(shù)組取第一個(gè)再比較，進(jìn)行100次，運(yùn)算次數(shù)是 100 * 100 = 10000 次

每次取數(shù)組的第一個(gè)元素比較，相同則比較第二個(gè)，依次排序

直接使用歸并排序就可以吧？而且只需要排出前一百個(gè)元素即可，其它的可以忽略。

這個(gè)問題的解法挺多，我可以給提供幾種思路：

假設(shè)問題抽象為 現(xiàn)在有 M 個(gè)數(shù)組，每個(gè)數(shù)組都有 U 個(gè)數(shù)。并且每個(gè)數(shù)組的元素都是從小到大排列的，
如何從中選出最小的前 K 個(gè)數(shù)。令 N = M * U。

直接排序
分配一個(gè)大小為 N 的數(shù)組 a，將輸入的 M 個(gè)數(shù)組的所有元素放入到 a 中，然后對 a 進(jìn)行升序排序，最后取 a 的前 K 個(gè)元素即為結(jié)果。時(shí)間復(fù)雜度 O(N*logN)，空間復(fù)雜度為 O(N)。

使用堆（TopK）
建立一個(gè)大小為 K 的 大頂堆，挨個(gè)遍歷每個(gè)數(shù)組，每次讓當(dāng)前數(shù)組元素 e 去和堆頂比較：

1. 堆中元素?cái)?shù)量不足 K 個(gè)，那么直接將 e 加入堆中
2. 堆中元素為 K 個(gè)，那么讓 e 和堆頂元素 t 去比較。如果 e < t，那么移除 t，并將 e 加入堆；否則直接丟棄 e。即堆中保留的是 {當(dāng)前堆中元素，e} 的 (K+1) 個(gè)元素中更小的那 K 元素。

所有數(shù)組遍歷完畢，那么堆中的 K 個(gè)元素即為結(jié)果。時(shí)間復(fù)雜度為 O(N*logK)，空間復(fù)雜度為 O(K)。

使用堆（優(yōu)化）
注意到這 M 個(gè)數(shù)組本身是有序的，因而我們可以利用到這個(gè)條件，我們假設(shè)每個(gè)數(shù)組都是升序排序的。
建立一個(gè)大小為 M 的 小頂堆，初始時(shí)將每個(gè)數(shù)組的第一個(gè)元素加入到堆中；建立一個(gè)容量為 K 的集合 S。

1. 從堆中取出堆頂元素（堆中最小元素，也是當(dāng)前所有數(shù)組元素中的最小元素） m，并放入到 S 中
2. 將 m 所在數(shù)組的下一個(gè)元素放入到堆中（因?yàn)?m 所在數(shù)組的下一個(gè)元素是除了堆中元素之外，最可能的那個(gè)最小元素）
3. 重復(fù) 1 和 2，直到 S 中的元素個(gè)數(shù)為 K —— 此時(shí) S 即最后的結(jié)果。

初始建堆的時(shí)間復(fù)雜度為 O(M*logM)；然后之后每次刪除元素和添加下一個(gè)元素調(diào)整堆的復(fù)雜度為 O(logM)，共需要調(diào)整 K 次，所以時(shí)間復(fù)雜度為 O(K*logM)；總的時(shí)間復(fù)雜度為 O((K+M)*logM)?？臻g復(fù)雜度為 O(c*M)，c 是大于 1 的常數(shù)，因?yàn)橐涗浢總€(gè)元素來自于哪個(gè)數(shù)組中，所以堆節(jié)點(diǎn)除了包含數(shù)組元素，還應(yīng)該包含其來源于哪個(gè)數(shù)組的信息，以及其下一個(gè)元素在數(shù)組中的位置的信息。