【Leetcode】179. Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

分析：给定一个正整数数组，将数组的数字整合成一个最大的数字。

样例：① [3, 30, 34, 5, 9]->9534330

　　　②[121,12]->12121

　　　③[0,0] -> 0

（1）将数组的数字组合，这隐含着一个大数问题，所以不可以直接用int或者long来保存结果，需要用到字符串（也可以用数组）.

（2）字符串m与字符串n拼接，可以成为mn或者nm。要比较mn与nm的大小，不能直接用Arrays.sort()函数，这个函数排序后的结果为升序，重写Comparator 实现降序，才能组成最大的数字。

(3)字符串m与n的大小比较规则：当mn>nm时，m>n；

　　　　　　　　　　　　　　　当mn=nm时，m=n；

　　　　　　　　　　　　　　　当mn<nm时，m<n；

(4)字符串的比较规则：str1="abcda";str2="abcdb";当比较到第五个字符str1为a，str2为b 。a的ASCII码小于b的ASCII码。所以str1<str2

下面的代码直接使用 Arrays.sort(com, new Comparator<Object>() { .....});在sort函数中重写 Comparator<Object>()，效率略低。跑完leetcode上的样例需要334ms。

public String largestNumber(int[] nums) {

        if (nums == null)

            return null;

        int len = nums.length;

        String[] com = new String[len];

        int all0 = ;

        for (int i = ; i < len; i++) {

            if (nums[i] == ) {

                all0++;

                System.out.println("~~~" + all0);

            }

            com[i] = Integer.toString(nums[i]);

        }

        Arrays.sort(com, new Comparator<Object>() {

            public int compare(Object obj1, Object obj2) {

                String str1 = (String) obj1;

                String str2 = (String) obj2;

                String com1 = str1 + str2;

                System.out.println("com1:" + com1);

                String com2 = str2 + str1;

                System.out.println("com2:" + com2);

                if (com1.compareTo(com2) >= ) {

                    System.out.println("com1<com2");

                    return -;

                } else {

                    System.out.println("com1>com2");

                    return ;

                }

            }

        });

        String ans = "";

        for (int i = ; i < len; i++) {

            ans += com[i];

        }

        if (all0 == len)

            ans = "";

        return ans;

    }

做出以下改进拍完样例的时间为120ms

Comparator<String> comp = new Comparator<String>() {

            @Override

            public int compare(String str1, String str2) {

                String s1 = str1 + str2;

                String s2 = str2 + str1;

                return s2.compareTo(s1);

                // reverse order here, so we can do append() later

            }

        };

        Arrays.sort(com, comp);

巴特西

【Leetcode】179. Largest Number

最新文章

热门文章