Leetcode: 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.

思路: 对于x和y两个数字,将x和y拼接,y和x凭借,如果x+y>y+x,则x>y。按照这样的规律给给定的数进行排序。

C++代码(使用了Lambda表达式):

class Solution
{
public:
    string largestNumber(vector<int> &num)
    {
        vector<string> strs;
        //将vector中的int转成string
        for_each(num.begin(), num.end(), [&](int i) {
            strs.push_back(to_string(i));
        });
        //将vector中的string进行排序,排序规则:如果x+y>y+x,则x>y
        sort(strs.begin(), strs.end(), [&](string x, string y) {
            return (x + y) > (y + x);
        });
        string result = "";
        //遍历vector中拍好像的string,将其连接起来
        for_each(strs.begin(), strs.end(), [&](string s) {
            //对都是0的情况,进行特殊处理
            if (result == "" && s == "0") return;
            result += s;
        });
        return result == "" ? "0" : result;
    }
};

C#代码:

public class Solution
{
    public string LargestNumber(int[] num)
    {
        string result = string.Empty;
        List<string> nums = new List<string>();
        foreach (int item in num)
        {
            nums.Add(item.ToString());
        }
        /*
         * Sort函数的原型是public void Sort(Comparison<T> comparison)
         * Comparison<T>是一个委托,其原型是public delegate int Comparison<in T>(T x, T y)
         * Comparison委托返回值:如果返回值为负,则x<y,为正,x>y,为0则相等
        */
        nums.Sort((string x, string y) =>
        {
            //strA.CompareTo(strB)方法如果返回负值,则strA>strB,正值strB<strA,0表示strA==strB
            return (y + x).CompareTo(x + y);
        });
        foreach (string item in nums)
        {
            if (result.Count() < 1 && item.Equals("0")) continue;
            result += item;
        }
        return result.Count() < 1 ? "0" : result;
    }
}

Python代码:

class Solution:
    # @param num, a list of integers
    # @return a string
    def largestNumber(self, num):
        strnum = []
        for item in num:
            strnum.append(str(item))
        strnum.sort(cmp = lambda x, y: cmp(x + y, y + x), reverse = True)
        result = ""
        for item in strnum:
            if (not result) and (item == "0"):
                continue
            result = result + item
        if not result:
            return "0"
        else:
            return result

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券