Python Relatively Simple Divide & Conquer Solution


  • 0
    C
    def select(s, k):
        pivot = s[len(s) // 2]
        sl, sp, sr = [], [], []
        for i in s:
            if i < pivot:
                sl.append(i)
            elif i == pivot:
                sp.append(i)
            else:
                sr.append(i)
        if k <= len(sl):
            return select(sl, k)
        elif k > len(sl) and k <= len(sl) + len(sp):
            return pivot
        elif  k > len(sl) + len(sp):
            return select(sr, k - len(sl) - len(sp))
    
    def medianSortedArrays(a, b):
        c = a + b
        length = len(c)
        oddmedian = select(c, 1 + length // 2)
        if length % 2 != 0:
            return oddmedian
        evenmedian = select(c, length // 2)
        return (oddmedian + evenmedian) / 2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.