[Leet Code] 179. Largest Number

[Level] Medium
[Topics] Array String Greedy Sorting

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.
Since the result may be very large, so you need to return a string instead of an integer.

Idea

 

---

Code (Not used Compare Function)

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        if len(nums) > 1:
            mid = len(nums) // 2 # mid is index
            L = nums[:mid]
            R = nums[mid:]
            self.largestNumber(L)
            self.largestNumber(R)

            i = j = k = 0                    # i, j, k is index
            while i < len(L) and j < len(R): # L and R left any index
                a = L[i]; a = str(a) # '3'
                b = R[j]; b = str(b) # '30'
                concat_ab = a + b; concat_ab = int(concat_ab) # 330
                concat_ba = b + a; concat_ba = int(concat_ba) # 303
            
                if concat_ab > concat_ba:
                    nums[k] = L[i] # 3
                    i += 1
                else :
                    nums[k] = R[j]
                    j += 1
                k += 1
            while i < len(L) : # L left any index
                nums[k] = L[i]
                i += 1
                k += 1
            while j < len(R) : # R left any index
                nums[k] = R[j]
                j += 1
                k += 1
        result = ''.join(str(num) for num in nums)
            # "000..." 같은 경우 처리
        return '0' if result[0] == '0' else result
        
        # Time Complexity : O(NlogN)
        # Space Complextiy : O(1)

---

Code (Used Compare Function)

class Solution:
    def compare(self, n1, n2):
        n1 = str(n1); n2 = str(n2)
        if int(n1+n2) > int(n2+n1):
            return int(n1)
        else :
            return int(n2)

    def largestNumber(self, nums: List[int]) -> str:
        if len(nums) > 1:
            mid = len(nums) // 2 # mid is index
            L = nums[:mid]
            R = nums[mid:]
            self.largestNumber(L)
            self.largestNumber(R)

            i = j = k = 0                    # i, j, k is index
            while i < len(L) and j < len(R): # L and R left any index
                nums[k] = self.compare(L[i], R[j])
                if nums[k] == L[i]:
                    i += 1
                else :
                    j += 1
                k += 1
            while i < len(L) : # L left any index
                nums[k] = L[i]
                i += 1
                k += 1
            while j < len(R) : # R left any index
                nums[k] = R[j]
                j += 1
                k += 1
        result = ''.join(str(num) for num in nums)
            # "000..." 같은 경우 처리
        return '0' if result[0] == '0' else result