179. Largest Number - cocoder39/coco39_LC GitHub Wiki

179. Largest Number

Notes 2022 Python custom sort which accepts 2 arguments

lambda

class Solution:             
    def largestNumber(self, nums: List[int]) -> str:
        compare = lambda a, b: -1 if a+b > b+a else 1
        
        nums = [str(num) for num in nums]
        nums.sort(key = functools.cmp_to_key(compare))
        return str(int(''.join(nums)))

custom sort

class Solution: 
    def cmp_func(self, x, y):
            """Sorted by value of concatenated string increasingly."""
            if x + y > y + x:
                return -1
            else:
                return 1
            
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(num) for num in nums]
        nums.sort(key=functools.cmp_to_key(self.cmp_func))
        return str(int(''.join(nums)))

=========================================

Notes 2020:

First idea was to create buckets so that number starts with 'i' will be put into bucket i (eg, 3, 33 go to bucket 3 and 9, 92 go to bucket 9). Then perform sort inside each bucket.

Given [3,30,34,5,9], this idea will produce result 9534303 while the correct result should be 9534330. Solving this by using customer comparator which checks the concatenation of two numbers to decide ranking.

class Solution:        
    def largestNumber(self, nums):
        
        def cmp_func(x, y):
            """Sorted by value of concatenated string increasingly."""
            if x + y > y + x:
                return -1
            elif x == y:
                return 0
            else:
                return 1
            
        # Build nums contains all numbers in the String format.
        nums = [str(num) for num in nums]
        
        # Sort nums by cmp_func decreasingly.
        nums.sort(key = functools.cmp_to_key(cmp_func))
        
        # Remove leading 0s, if empty return '0'.
        return ''.join(nums).lstrip('0') or '0'

========================================================================================

very smart ideas of customizing comparator.

tip: res[0] == "0" means res is a series of '0'.

O(n * log n) time and O(n) memory

string largestNumber(vector<int>& nums) {
        vector<string> strs;
        for (auto num : nums) {
            strs.push_back(to_string(num));
        }
        sort(strs.begin(), strs.end(), [](string s1, string s2) {
            return s1 + s2 > s2 + s1;    
        });
        
        string res;
        for (auto str : strs) {
            res += str;
        }
        return res[0] == '0' ? "0" : res;
    }
⚠️ **GitHub.com Fallback** ⚠️