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.
题目大意：
给一组数字，让这些数字字符串组成一个最大的数，这个数可能很大，用字符串表示。
思路：
采用冒泡排序，将数字字符串排序，然后将它们连接起来。
比较两个数字字符串，通过比较s1+s2 与s2+s1的大小，来确定哪个大。
代码如下：
|
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
|
class
Solution {
public
:
string largestNumber(vector<
int
>& nums) {
vector<string > numstr;
for
(
int
i = 0; i < nums.size(); i++)
{
stringstream ss;
ss << nums[i];
numstr.push_back(ss.str());
}
string tmp;
for
(
int
i = 0; i < numstr.size(); i++)
{
for
(
int
j = 0; j < numstr.size() - i - 1; j++)
{
if
(
strcmp
((numstr[j] + numstr[j + 1]).data(),
(numstr[j + 1] + numstr[j]).data()) > 0)
//strcmp((numstr[j] + numstr[j + 1]).data(), (numstr[j + 1] + numstr[j]).data())
{
tmp = numstr[j];
numstr[j] = numstr[j+1];
numstr[j + 1] = tmp;
tmp.clear();
}
}
}
string result;
for
(
int
i = numstr.size() - 1; i >= 0; --i)
{
//极端情况，最大的数字是0，则直接返回"0"
if
(numstr[numstr.size() - 1] ==
"0"
)
return
"0"
;
result += numstr[i];
}
numstr.clear();
return
result;
}
};
|
网上优秀解答方案：
参考：https://discuss.leetcode.com/topic/7286/a-simple-c-solution
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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;
}
};
|
其中sort第三个参数用到了lambda表达式，这是C++11的一个扩展。
关于lambda表达式
参考http://www.cnblogs.com/zhuyp1015/archive/2012/04/08/2438176.html
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1837818
