【字符串排序】n个数连接得到最小或最大的多位整数-阿里云开发者社区

【字符串排序】n个数连接得到最小或最大的多位整数

2017-11-14 1630

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

算法分析

　　此题很容易想到使用贪心法。

　　把整数按从大到小的顺序连接起来，测试题目的例子也都符合，但最后测试的结果却不全对。按这种贪心标准，我们很容易找到反例：12，121 应该组成12121而非12112，那么是不是相互包含的时候就从小到大呢？也不一定，如：12，123 就是12312而非12112,这样情况就有很多种了。

　　是不是此题不能用贪心法呢？

　　其实此题是可以用贪心法来求解，只是刚才的贪心标准不对，正确的贪心标准是：先把整数化成字符串，然后再比较a+b和b+a，如果a+b>b+a，就把a排在b的前面，反之则把a排在b的后面。

　　举例说明正常的字符串比较缺陷！如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上'32132' < '32321'。

　　所以，自定义一种字符串的比较规则：

　　如果A+B>B+A,则我们认为A>B。

　　且可以证明：如果A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。

　　这样一来，程序就很简单了。分3步：

　　（1）先把n个数字转换成字符串存储；

　　（2）按照自定义的规则把n个字符串从大到小排序；

　　（3）依次输出这些字符串。

代码

 1 #include <iostream>
 2 #include <sstream>
 3 #include <string>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 string int2str(int num) {
 9     stringstream ss;
10     ss << num;
11     return ss.str();
12 }
13 
14 int main()
15 {
16     vector<string> v;
17     int num;
18 
19     while (cin>>num) {
20         v.push_back(int2str(num));
21     }
22     for (unsigned int i = 0; i < v.size()-1; i++) {
23         for (unsigned int j = 0; j < v.size()-i-1; j++) {
24             if ((v[j] + v[j+1]) < (v[j+1]+v[j])) {
25                 swap(v[j], v[j+1]);
26             }
27         }
28     }
29 
30     for (unsigned int i = 0; i < v.size(); i++) {
31         cout<<v[i];
32     }
33     return 0;
34 }