My Java solution. By figuring out an order for the elements


  • 0
    G

    Find it very hard to explain:
    First I converted all the int elements to strings. And then I wrote a compareTo method to give the strings elements an order.

    assume there are two strings s1 = a1 a2 a3 a4 a5 a6 a7 and s2 = b1 b2 b3 and s1 is the longer one.
    The comparison has two parts:
    compare a1a2a3 with b1b2b3, then a4a5a6 with b1b2b3, then a7 with b1 using normal string comparison. If any comparison gives -1 or 1, done.

    If they are all equal, here's the tricky part. Now we should actually begin comparing b2 b3 with b1 b2. If b2b3 > b1b2, then we should put s2 in front of s1.

    public String largestNumber(int[] num) {
            if (num == null || num.length == 0) return "";
            NumberString[] strs = new NumberString[num.length];
            for (int i=0; i<num.length; i++) {
                strs[i] = new NumberString(num[i]);
            }
            Arrays.sort(strs);
            if (strs[0].str.equals("0")) 
                return "0";
                
            StringBuilder sb = new StringBuilder();
            for (NumberString s : strs) {
                sb.append(s.str);
            }
            return sb.toString();
        }
        
        public class NumberString implements Comparable<NumberString> {
            String str;
            public NumberString(int n) {
                str = n + "";
            }
            
            public int compareTo(NumberString other) {
                int i=0, j=0;
                String s1 = str, s2 = other.str;
                while (i < s1.length() && j < s2.length()) {
                    if (s1.charAt(i) > s2.charAt(j)) {
                        return -1;
                    } else if (s1.charAt(i) < s2.charAt(j)) {
                        return 1;
                    }
                    i += 1;
                    j += 1;
                }
                while (i != s1.length()) {
                    if (j == s2.length()) {
                        j = 0;
                    }
                    if (s1.charAt(i) > s2.charAt(j)) {
                        return -1;
                    } else if (s1.charAt(i) < s2.charAt(j)) {
                        return 1;
                    }
                    i += 1;
                    j += 1;
                } 
                while (j != s2.length()) {
                    if (i == s1.length()) {
                        i = 0;
                    }
                    if (s1.charAt(i) > s2.charAt(j)) {
                        return -1;
                    } else if (s1.charAt(i) < s2.charAt(j)) {
                        return 1;
                    }
                    i += 1;
                    j += 1;
                }
                if (i == s1.length() && j == s2.length()) return 0;
                if (i == s1.length()) {
                    int tmp = j;
                    while (j < s2.length()) {
                        if (s2.charAt(j) < s2.charAt(j-tmp)) {
                            return -1; 
                        } else if (s2.charAt(j) > s2.charAt(j-tmp)) {
                            return 1;
                        }
                        j += 1;
                    }
                } else {
                    int tmp = i;
                    while (i < s1.length()) {
                        if (s1.charAt(i) < s1.charAt(i-tmp)) {
                            return 1;
                        } else if (s1.charAt(i) > s1.charAt(i-tmp)) {
                            return -1;
                        }
                        i += 1;
                    }
                }
                return 0;
            }
        }

Log in to reply
 

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