给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。
样例
给出 [1, 20, 23, 4, 8],返回组合最大的整数应为8423201。
九章算法找到的Solution如下
#include <sstream>
bool cmp(const string s1, const string s2) {
return (s1 + s2) > (s2 + s1);
}
class Solution {
public:
/**
*@param num: A list of non negative integers
*@return: A string
*/
string largestNumber(vector<int> &num) {
// write your code here
vector<string> s_num(num.size());
stringstream stream;
for (int i = 0; i < num.size(); ++i) {
stream << num[i];
stream >> s_num[i];
stream.clear();
}
sort(s_num.begin(), s_num.end(), cmp);
string tmp_res;
for (int i = 0; i < s_num.size(); ++i) {
tmp_res += s_num[i];
}
string res;
bool flag = false;
for (int i = 0; i < tmp_res.size(); ++i) {
if (tmp_res[i] != '0') {
res.push_back(tmp_res[i]);
flag = true;
} else if (flag) {
res.push_back(tmp_res[i]);
}
}
if (!flag) res.push_back('0');
return res;
}
};
在设flag得到res那部分没看明白,
能给讲解下吗
可以把这段代码分成两部分看。正常情况下,代码把下面的for循环执行完就结束了:
for (int i = 0; i < s_num.size(); ++i) {
tmp_res += s_num[i];
}
例如,按照cmp排序[1, 20, 23, 4, 8],得到[8, 4, 23, 20, 1]。用一个for循环把它们连接成“8423201”就是最终答案。
但是,总有特殊情况出现。如果数组里面全是0呢?例如,[0, 0, 0, 0]。这时就要对tmp_res进行处理:遍历tmp_res,有三种情况:
如果当前字符不是'0',就把当前字符存储到res;
如果当前字符是'0',但是tmp_res里面存在不是'0'的字符,同样把当前字符存储到res;
如果当前字符是'0',而且当前字符之前的所有字符都是'0',就不做处理。
遍历结束后,如果发现flag为false,说明数组里全是0,所以往res里保存一个'0'即可。
这部分的作用是.. 如果所有位都是0, 比如输入是[0,0,0,0], 让这个函数返回0而不是0000
flag
表示tmp_res[i]左边是否有非0的位