486. Merge K Sorted Arrays

LintCode 炼码 - ChatGPT！更高效的学习体验！

Divide and conquer 分治，两两merge，直到成为一个。

跟 Q88 的关系就像Q21 -> Q23.

88. Merge Sorted Array21. Merge Two Sorted Lists23. Merge k Sorted Lists

class Solution:
    """
    @param arrays: k sorted integer arrays
    @return: a sorted array
    """
    def mergekSortedArrays(self, arrays):
        # write your code here
        def mergeTwoSortedArrays(a, b):
            res = []
            m, n = len(a), len(b)
            i, j = 0, 0
            while i < m or j < n:
                if i == m: 
                    res.append(b[j])
                    j += 1 
                elif j == n:
                    res.append(a[i])
                    i += 1 
                elif a[i] >= b[j]:
                    res.append(b[j])
                    j += 1 
                else:
                    res.append(a[i])
                    i += 1 
            return res
        
        n, skip = len(arrays), 1 
        while skip < n:
            for a in range(0, n-skip, skip*2):
                arrays[a] = mergeTwoSortedArrays(arrays[a], arrays[a+skip])
            skip *= 2 
        return arrays[0]