My Python solution to share,use mergeSort


  • 0
    L

    Since we can realize that AB > BA,A should be put in front of B

    class Solution:
        # @param {integer[]} nums
        # @return {string}
        def largestNumber(self, num):
            num = [str(x) for x in num]
            num = self.mergeSort(num)
            return str(int("".join(num)))
        
        def mergeArray(self,left, right):
            """
                merge the left and right array
            """
            res = []
            i = j = 0
            while i < len(left) and j < len(right):
                if int(left[i] + right[j]) < int(right[j] + left[i]):
                    res.append(right[j])
                    j += 1
                else:
                    res.append(left[i])
                    i += 1
            while i < len(left):
                res.append(left[i])
                i += 1
            
            while j < len(right):
                res.append(right[j])
                j += 1
            return res
                    
        def mergeSort(self,lists):
            if len(lists) <= 1:
                return lists
            mid = int(len(lists)/2)
            left = self.mergeSort(lists[:mid])
            right = self.mergeSort(lists[mid:])
            return self.mergeArray(left,right)
    

Log in to reply
 

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