Largest Number

Question

Given a list of non negative integers, arrange them such that they form the largest number. Have you met this question in a real interview? Yes Example Given [1, 20, 23, 4, 8], the largest formed number is 8423201.

Thoughts

arrange is complicated, let's just say we are adding the numbers to the front one by one, so we just need to find a order to add numbers.

if the current value is n, we have two strings a and b, if could be abn or ban.

so we just need to compare ab and ba.

for java, we can use comparator. for python, we can also define our own compare function with cmp parameter example

>>> def numeric_compare(x, y):
        return x - y
        >>> sorted([5, 2, 4, 1, 3], cmp=numeric_compare)
        [1, 2, 3, 4, 5]

• positive means x > y
• 0 means x == y
• negative means x < y

python sort

notes:

• python cmp needs to return a int not long, so I convert the code below to avoid big number

Solution

python, sorted() with cmp

class Solution:    
    #@param num: A list of non negative integers
    #@return: A string
    def largestNumber(self, num):
        # write your code here
        res = ""
        if not num:
            return ""
        strs = []
        for n in num:
            strs.append(str(n))

        newList = sorted(strs, cmp=self.stringCompare)

        if newList[0] == "0":
            return "0"

        for l in newList:
            res += l

        return res

    def stringCompare(self, s1, s2):
        s1As2 = s1 + s2
        s2As1 = s2 + s1
        if int(s2As1) > int(s1As2):
            return 1
        elif int(s2As1) == int(s1As2):
            return 0
        else:
            return -1

java comparator

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] num) {
        // write your code here
        StringBuilder res = new StringBuilder();
        if ( num == null || num.length == 0) {
            return res.toString();
        }

        String[] str = new String[num.length];
        for(int i = 0; i < num.length; i++) {
            str[i] = num[i] + "";
        }
        Comparator<String> comp = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                String s1as2 = s1 + s2;
                String s2as1 = s2 + s1;
                return s2as1.compareTo(s1as2);
            }
        };
        Arrays.sort(str, comp);
        if (str[0].equals("0")) {
            return "0";
        }
        for (String s : str) {
            res.append(s);
        }
        return res.toString();

    }
}