My java based solution using a recursive comparator


  • 0
    M
    import java.util.Collections;
    import java.util.Comparator;
    import java.util.Iterator;
    import java.util.LinkedList;
    
    public class Solution {
    
    	public String largestNumber(int[] num) {
    
    		LinkedList<Number> numList = new LinkedList<Number>();
    		for (int i = 0; i < num.length; i++) {
    			numList.add(new Number(num[i]));
    		}
    
    		Collections.sort(numList, new NumberComparator());
    
    		StringBuffer sb = new StringBuffer();
    		for (Number number : numList) {
    			sb.append(new Integer(number.num).toString());
    		}
    
    		return removeTrailingZeros(sb.toString());
    	}
    
    	private String removeTrailingZeros(String str) {
    		int zeroCount = 0;
    		for (int i = 0; i < str.length(); i++) {
    			if (str.charAt(i) == '0')
    				zeroCount++;
    		}
    		return (zeroCount == str.length() ? "0" : str);
    	}
    
    }
    
    class Number {
    	int num;
    	LinkedList<Integer> digits = new LinkedList<Integer>();
    
    	public Number(int num) {
    		this.num = num;
    
    		int val = num;
    
    		while (val != 0) {
    			digits.addFirst(val % 10);
    			val = val / 10;
    		}
    		
    		if (num == 0)
    			digits.addFirst(0);
    	}
    
    	public Number() {
    	}
    
    };
    
    class NumberComparator implements Comparator<Number> {
    
    	@Override
    	public int compare(Number o1, Number o2) {
    
    		Iterator<Integer> iter1 = o1.digits.iterator();
    		Iterator<Integer> iter2 = o2.digits.iterator();
    
    		while (iter1.hasNext() && iter2.hasNext()) {
    			int dig1 = iter1.next();
    			int dig2 = iter2.next();
    
    			if (dig1 > dig2)
    				return -1;
    			else if (dig2 > dig1)
    				return 1;
    		}
    
    		if (!iter1.hasNext() && !iter2.hasNext())
    			return 0;
    
    		else if (!iter1.hasNext()) {
    			Number newNum = new Number();
    			while (iter2.hasNext()) {
    				newNum.digits.add(iter2.next());
    			}
    			return compare(o1, newNum);
    		} else {
    			Number newNum = new Number();
    			while (iter1.hasNext()) {
    				newNum.digits.add(iter1.next());
    			}
    			return compare(newNum, o2);
    		}
    	}
    }

Log in to reply
 

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