题目
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.
原题链接： https://oj.leetcode.com/problems/largest-number/
算法分析
case1（一般情况）：
[3, 30, 34, 5, 9] -> (9 -> 5 -> 34 -> 3 -> 30) -> 9534330
直观想法按位从高到底排序
可以很容易得到9->5的顺序，然而接下来问题来了，位相等的情况怎么办?
考虑3，30，34（数字组1）
简单考虑[3, 30]，显然3->30要比30->3的值更大，即3>30的个位0；
再考虑[3, 34]，(34->3) > (3->34)，即34的个位4>3；
最后[30, 34]，34 > 30；
所以数字组1的排序为34->3->30；
最终结果为9->5->34->3->30
case2（不止一位相等，多位高位相等的情况）：
[824, 8247] -> (824 -> 8247) -> 8248247
逐一从高位到低位比较，那么第二个数字的最低位7应该与第一个数字的哪位比较呢？决定这两数顺序的不外乎，824->8247，8247->824这两种情况，直观上7应与第一个数字的第一位8比较，由于7<8，所以824->8247
case3 （不止一位相等，多位高位相等的情况）：
[824, 82483] -> (82483 -> 824) -> 82483824
case4（重复数字）：
[33, 333] -> 33333
一般考虑假设待比较的数字为a1a2, b1b2b3，a1b1…均为位；在重复数字的情况下
如
a1 a2
|| ||
b1 b2 b3
且b3 == a1，b1 == a2，此时可以得到b1 == a1 == a2 == b2 == b3，即全等，因此最大的比较次数为数字1的位数加数字2的位数 - 1次，该例子的情况为4次。
题目陷阱
case1（有数字为0）：
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
case2（数字均为0）：
[0, 0]
算法设计
Integer类，将int按位存储，next取出下一位方法；
class Integer {
public:
Integer(int i);
int getCount() { return count; }
int next() {
if (!tmp_count) {
tmp_count = count;
}
return digits[--tmp_count];
}
private:
int _i;
int count;
int tmp_count;
int digits[];
};
Integer::Integer(int i):count(),tmp_count() {
// there has a great trap when i == 0
if (i) {
while (i) {
digits[count++] = i % ;
i /= ;
}
} else {
++count;
digits[] = ;
}
tmp_count = count;
}
比较函数cmp，按位从高到低循环比较，等于最大比较次数后退出；
bool cmp(const int& a, const int& b) {
Integer ia(a);
Integer ib(b);
int maxCmpCount = ia.getCount() + ib.getCount() - ;
int curCmpCount = ;
while (curCmpCount < maxCmpCount) {
int bita = ia.next();
int bitb = ib.next();
if (bita > bitb) {
return true;
}
if (bita < bitb) {
return false;
}
++curCmpCount;
}
return false;
}
完整代码（Runtime：9ms）
#include <string>
#include <vector>
#include <cstdio> class Integer {
public:
Integer(int i); int getCount() { return count; } int next() {
if (!tmp_count) {
tmp_count = count;
}
return digits[--tmp_count];
} private:
int _i;
int count;
int tmp_count;
int digits[];
}; Integer::Integer(int i):count(),tmp_count() { // there has a great trap when i == 0
if (i) {
while (i) {
digits[count++] = i % ;
i /= ;
}
} else {
++count;
digits[] = ;
}
tmp_count = count;
} bool cmp(const int& a, const int& b) {
Integer ia(a);
Integer ib(b); int maxCmpCount = ia.getCount() + ib.getCount() - ;
int curCmpCount = ; while (curCmpCount < maxCmpCount) {
int bita = ia.next();
int bitb = ib.next(); if (bita > bitb) {
return true;
} if (bita < bitb) {
return false;
} ++curCmpCount;
} return false;
} class Solution {
public:
std::string largestNumber(std::vector<int> &num) {
// there is a trap when nums is all zero
bool allZero = true;
for (auto itr = num.begin(); allZero && itr != num.end(); ++itr) {
if (*itr != ) {
allZero = false;
}
} if (allZero) {
return std::string("");
} std::sort(num.begin(), num.end(), cmp);
std::string rel;
char tmp[];
for (auto itr = num.begin(); itr != num.end(); ++itr) {
sprintf(tmp, "%d", *itr);
rel += tmp;
}
return rel;
}
};