Java code by providing comparator, with explaination, O(nlogn)


  • 13
    D

    Some useful test case before you start: { 0,0 }, { 12,121 }.

    public String largestNumber(int[] num) {
            StringBuilder res = new StringBuilder();
    		if (num == null || num.length == 0)
                return null;
            
            //conver Integer to string
            String[] nums = new String[num.length];
            for (int i = 0; i < num.length; i++)
                nums[i] = Integer.toString(num[i]);
                
            //Define comparator
            Comparator<String> comp = new Comparator<String>()
                    {
                        @Override
                        public int compare(String o1, String o2)
                        {
                        	return (o1+o2).compareTo(o2+o1);
                        }
                    };
             Arrays.sort(nums, comp);
             
             //The new number should not start with 0 unless it is 0
            if (nums[nums.length-1].equals("0")) 
                return "0";
           
            for (int i = nums.length-1; i >= 0; i--)
             {
            	 res.append(nums[i]);
             }
            
            return res.toString();
        }

  • 0
    I

    Good solution, just wanted to comment that the time complexity will be O(nlogn) due to the sort part.


  • 0
    D

    Oops, silly me.


Log in to reply
 

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