leetcode 179 最大数 排序

缘起

日常浪费生命 ~ leetcode 179 最大数

分析

1
2
3
4
5
6
7
8
9
10
11
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

此题如果意识到 a和b这两个非负整数, 如果 a1a2,…,an 是最大的那个序列的话, 则一定满足如下性质

任何两个相邻的元素交换之后一定不会比现在的大

这个性质是显然的——不然的话，就可以搞的更大.

所以我们只需要将输入的非负整数按照这种自定义规则sort一下，然后用字符串输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public:
	string largestNumber(vector<int>& nums) {
		string ans;
		sort(nums.begin(), nums.end(), Solution::cmp);
		for (vector<int>::iterator vit = nums.begin(); vit!=nums.end(); vit++)
		{
			stringstream ss;
			ss << *vit;
			ans.append(ss.str());
		}
		reverse(ans.begin(), ans.end());
		while(ans.length()&&ans.back()=='0') // 去掉前导0
		{
			ans.pop_back();
		}
		reverse(ans.begin(), ans.end());
		if (!ans.length())
		{
			ans = "0";
		}
		return ans;
	}

	bool static cmp(int a, int b) // 返回true表示a<b, 排序要排在前面
	{
		string aa,bb;
		stringstream ss;
		ss << a;
		aa = ss.str();
		ss.clear();
		ss.str("");
		ss << b;
		bb = ss.str();
		string kk = aa;
		string s1 = aa.append(bb), s2 = bb.append(kk); // append将改变原先的字符串
		if (s1>s2) // 则a应该排在b前面, 排序之后就是ab而不是ba
		{
			return true;
		}
		return false;
	}
};

只想说 stringstream 真香!!!

ac情况（水过水过~）

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
72 ms
, 在所有 C++ 提交中击败了
5.26%
的用户
内存消耗 :
8.8 MB
, 在所有 C++ 提交中击败了
85.85%
的用户