剑指Offer - 九度1504 - 把数组排成最小的数

剑指Offer - 九度1504 - 把数组排成最小的数
2014-02-06 00:19
题目描述:

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

输入:

输入可能包含多个测试样例。
对于每个测试案例,输入的第一行为一个整数m (1<=m <=100)代表输入的正整数的个数。
输入的第二行包括m个正整数,其中每个正整数不超过10000000。

输出:

对应每个测试案例,
输出m个数字能排成的最小数字。

样例输入:
3
23 13 6
2
23456 56
样例输出:
13236
2345656
题意分析:
  将一组数字从左到右连起来,使得组成的一个大数最小。
  我首先想到的方法,当然是写一个自定义的比较函数,然后使用qsort或者sort来将数组排好序,连接起来即可。
  问题是:这个比较函数怎么写呢?
  我的第一次尝试,是将两个数字逐位进行比较,但有一种问题:123、1231、1230、12312、123123,这些数字谁该放前面呢?
  不难看出来,上面的情况就是存在前缀的情况。我尝试写了一版代码,自测通过但是提交后Wrong Answer。
  想了几分钟还是没想出问题,于是觉得应该更简单粗暴点。对于两个数字x和y,直接看看谁放前面的结果比较小,就把谁放前面。
  比较函数非常简单,请参见代码。为了方便起见,直接用string来表示数字。
  时间复杂度O(n * log(n)),源于sort的调用,空间复杂度O(1)。
剑指Offer - 九度1504 - 把数组排成最小的数
 1 // 689366    zhuli19901106    1504    Accepted    点击此处查看所有case的执行结果    1524KB    771B    270MS
 2 // 201402022141
 3 #include <algorithm>
 4 #include <iostream>
 5 #include <string>
 6 #include <vector>
 7 using namespace std;
 8 
 9 vector<string> vv;
10 int n;
11 
12 bool comparator(const string &x, const string &y)
13 {
14     string s1, s2;
15 
16     s1 = x + y;
17     s2 = y + x;
18     return s1 < s2;
19 }
20 
21 int main()
22 {
23     string s;
24     int i;
25 
26     while (cin >> n) {
27         vv.clear();
28         for (i = 0; i < n; ++i) {
29             cin >> s;
30             vv.push_back(s);
31         }
32         sort(vv.begin(), vv.end(), comparator);
33         s = "";
34         for (i = 0; i < n; ++i) {
35             s = s + vv[i];
36         }
37         for (i = 0; i < (int)s.length() - 1; ++i) {
38             if (s[i] != 0) {
39                 break;
40             }
41         }
42         s = s.substr(i, s.length() - i);
43         cout << s << endl;
44     }
45 
46     return 0;
47 }
剑指Offer - 九度1504 - 把数组排成最小的数

剑指Offer - 九度1504 - 把数组排成最小的数

上一篇:剑指Offer - 九度1503 - 二叉搜索树与双向链表


下一篇:Hadoop学习笔记—2.不怕故障的海量存储:HDFS基础入门