LeetCode-179. Largest Number

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.

由题意可以知道，结果最大数字符串是由这些数字转成字符串后按其降序排列而来。理解这一点这道题就简单了。

另外需要考虑一些特殊情况：如全是0的情况、为空的情况等等。

class Solution {

public:

    string largestNumber(vector<int>& nums) {

        string result;

		vector<string> arr;

		for (const auto n:nums)

		{

			arr.push_back(to_string(n));

		}

		sort(arr.begin(), arr.end(), [](const string& s1, const string& s2){return s1 + s2 > s2 + s1; });

		for (const auto& e:arr)

		{

			result += e;

		}

		if (result.at(0) == '0')

		{

			return "0";

		}

		return result;

    }

};

上面代码是先将int窗口转成相应string的容器，然后对string容器中string进行降序排序，最后排序后的string拼接成一个字符串，再排除特殊情况即可。

下面给出的方法从代码角度来看更简洁，但性能方面会差一点，因在排序过程，每两个int转成字符串比较过程中，每次to_string都会构造一个string, 然后两个string再进行+运算符，最后两个string再进行>运算符，额外开销有点大。

class Solution

{

public:

	string largestNumber(vector<int>& nums)

	{

		string result;

		if (nums.empty())

		{

			return "0";

		}

		sort(nums.begin(), nums.end(),

			[](const int n1, const int n2){return to_string(n1) + to_string(n2) > to_string(n2) + to_string(n1); });

		for (const auto e:nums)

		{

			result += to_string(e);

		}

		if (result.at(0) == '0')

		{

			return "0";

		}

		return result;

	}

};

上面两种方法在leetcode上模拟运行，方法1运行大概8ms, 方法2大概28ms, 主要性能消耗还是在排序过程中对int数据按字符串比较排序，不断地string隐式构造及string运算符+及>的重载。其实这里我们可以将及单独实现，优化掉这块的消耗。

class Solution

{

	static bool intAsstrCompare(int a, int b)

	{

		char aBuf[64];

		char bBuf[64];

		memset(aBuf, 0, sizeof(aBuf));

		memset(bBuf, 0, sizeof(bBuf));

		sprintf(aBuf, "%d%d", a, b);

		sprintf(bBuf, "%d%d", b, a);

		return strcmp(aBuf, bBuf) > 0;

	}

public:

	string largestNumber(vector<int>& nums)

	{

		string result;

		if (nums.empty())

		{

			return "0";

		}

		sort(nums.begin(), nums.end(), intAsstrCompare);

		for (const auto e:nums)

		{

			result += to_string(e);

		}

		if (result.at(0) == '0')

		{

			return "0";

		}

		return result;

	}

};

上面代码运行后为12ms, 竟然还没有方法1快！！！有兴趣的可以接着去研究一下。

巴特西

LeetCode-179. Largest Number

179. Largest Number

最新文章

热门文章