题解 | #最小的K个数#

本来想练习 merge sort 做了个这

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        tinputSorted = self.MergeSort(tinput)
        return tinputSorted[:k]
    def MergeSort(self, tinput):
        #merge sort
        iListLen = len(tinput)
        if iListLen <= 1:
            return tinput
        iMiddle = int(iListLen/2)
        lLeftList = self.MergeSort(tinput[:iMiddle])
        lRightList = self.MergeSort(tinput[iMiddle:])
        C = self.Merge(lLeftList,lRightList)
        return C

    def Merge(self,lLeft,lRight):
        # Merge
        C = []
        i = 0
        j = 0
        lLeft.append(None)
        lRight.append(None)
        while (lLeft[i] is not None) and (lRight[j] is not None):
            if lLeft[i] <= lRight[j]:
                C.append(lLeft[i])
                i += 1
            else:
                C.append(lRight[j])
                j += 1
        if lLeft[i] is None:
            for jj in lRight[j:-1]: C.append(jj)
        else:
            for ii in lLeft[i:-1]: C.append(ii)
        return C