Largest Number

今天是一道关于贪婪算法的题目，来自LeetCode（#179），难度为Medium，Acceptance为16.9%，通过率已经很低了。

题目如下

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.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.

思路如下

这道题目的思路较为简单，主要是细节部分容易出错。我们以输入两个数9, 97为例，将这两个数组成一个大数后可以得到997,979，此时很容易比较这两个数，得到较大的数是997，那么这个数和原来的两个数有什么关系呢。

如果我们之间将9, 97排序，然后将较大的数放在前，较小的数在后，得到979显然不对，可行的方法是将两个数都做为字符串，然后进行字符串拼接，这时就可以得到两个字符串形式的997,979，然后用字符串比较，此时的比较结果与数字的比较结果是相同的。

将上述两个数的比较思路推广到整个数组就可以得到整个数组的排序方法，然后将排序后的数字拼到一起，就是我们要求的结果。

注意：当最大的数字是0时，说明此时输入的数组中仅包括1个或多个0，此时直接返回结果0，若此时继续做字符串拼接，可能返回00这样的结果，是错误的。

代码如下

java版

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] num) {
        // write your code here
        String[] strs = new String[num.length];
        for(int i = 0; i < num.length; i++) {
            strs[i] = "" + num[i];
        }
        Comparator comparator = new Comparator<String>() {
            public int compare(String str1, String str2) {
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return 0 - s1.compareTo(s2);
            }
        };
        Arrays.sort(strs, comparator);
        if(strs[0].equals("0"))
            return "0";
        StringBuilder builder = new StringBuilder();
        for(String str : strs) {
            builder.append(str);
        }
        return builder.toString();
    }
}

c++版

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> arr;
        for(auto i:num)
            arr.push_back(to_string(i));
        sort(begin(arr), end(arr), [](string &s1, string &s2){ return s1+s2>s2+s1; });
        string res;
        for(auto s:arr)
            res+=s;
        while(res[0]=='0' && res.length()>1)
            res.erase(0,1);
        return  res;
    }
};

如果觉得文章有帮助的话，不妨关注一下本公众号，当然也希望能帮作者推广一下，更多人关注我也会更有动力，在此先谢过了。

关注我
该公众号会每天推送常见面试题，包括解题思路是代码，希望对找工作的同学有所帮助

image