Fast C# solution using two comparers : beats 96% O(nlogn) O(1)


  • 0
    G
    public class Solution {
    public string LargestNumber(int[] nums) {
        if(nums == null){
            return null;
        }
        
        if(nums.All(x => x == 0)){ return "0"; }
        
        var comp = new MyComparer();
        var rcomp = new ReverseComparer();
        
        return string.Join(string.Empty, nums.Select(x => x.ToString()).OrderByDescending(x => x, comp).ThenByDescending(x=> x, rcomp));
    }
    
    public class MyComparer : IComparer<string>
    {
        public int Compare(string left, string right)
        {
           var longest = left.Length > right.Length ? left : right;
           for(int i = 0; i< longest.Length;  i++){
               var l =i < left.Length ? left[i] : left[0];
               var r = i < right.Length ? right[i] : right[0];
               
               if(l>r){ return 1; }
               else if(l<r) { return -1; }
           }
    
           return 0;
        }
    
    }
    
    public class ReverseComparer : IComparer<string>
    {
        public int Compare(string left, string right)
        {
           for(int i = 0; i< Math.Min(left.Length, right.Length); i++){
               var l = left[left.Length -1-i];
               var r = right[right.Length -1-i];
               
               if(l>r){ return 1; }
               else if(l<r) { return -1; }
           }
           
           if( left.Length == right.Length){
               return 0;
           }
           else if( left.Length < right.Length){
               return -1;
           }
           else{
               return 1;
           }
        }
    }
    }
    

    This is the explanation :

    • Notice that if all the numbers are the same length, it is easy : we just need to sort them in descending order
    • To avoid the problem of having different size numbers we can pad the right of the number with the first digit. Indeed when comparing 3,34 and 32, I want to order them like 34,33,32 which i can achieve by considering 3 as 33. What matters is that the last number is equal to the first one : if you want too order 824 and 8247 you want to have 824 first because it will create 8248 first which is bigger than 8247
    • the last problem occurs when the numbers, once padded are equals. Eg: 12 and 121. The solution is then to order them from the end (reversing the number if you prefer). Indeed, 121 will be padded as 121, so we need to consider how we wold like to order 12 and 121. Again what we ant is to have the biggest number first, which we can achieve by ordering from the right to left. In this example(12,121) the way to have the biggest number first is to have the '2' digit as fast as possible. Now consider the example 1211,121 to see the need for reverse sorting.

    We can achive those two special sort using custom comparer :

    • the first comparer will consider the padding to the right of the number
    • the second comparer will sort from right to left

Log in to reply
 

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