n 個有序組中的 n 個最小數

題：給n 個有序數組，每個數組有n個數，一共n^2個數，輸出其中n個最小的數
例：S1 = [0,4,19,20] S2 =[1,45,67,99] S3= [2,3,17,19] S4=[11,21,31,41]  輸出 S = [0,1,2,3]
想請問各位大神有沒有時間複雜度O(nlogn)的解法？我想說取出每個數列中的第一個數形成最小堆，然後再取最小數組成輸出數組，直到輸出數組有n個數，但是一共有n^2個數 這樣時間複雜度是不是就是O(n^2logn)?

没理解错的话，每次存一个pair，数字本身和是从哪个数组里拿的
这样每次min heap拿走min（logn），再从对应数组取下一个值加入heap（logn）
一共拿走n个最小，就是nlogn
这样理解对吗？

歸並排序算法可以實現O(n)的時間複雜度的，比O(n)還要優秀

补充内容 (2021-2-25 10:59):
喔喔喔看錯題了不好意思

shzhangyihan 发表于 2021-02-24 19:26:46
没理解错的话，每次存一个pair，数字本身和是从哪个数组里拿的
这样每次min heap拿走min（logn），再从对应数组取下一个值加入heap（logn）
一共拿走n个最小，就是nlogn

赞，而且c/c++ 可以直接存pointer

shzhangyihan 发表于 2021-2-25 11:26
没理解错的话，每次存一个pair，数字本身和是从哪个数组里拿的
这样每次min heap拿走min（logn），再从对 ...

感謝！！！ 這樣應該就是O(nlogn)

是不是有点像刷题网散其把？