问题：
给出一组非负整数，重新排列他们的顺序把他们组成一个最大的整数。
样例：
给出 [1, 20, 23, 4, 8]，返回组合最大的整数应为8423201。
挑战：
时间复杂度：O(nlogn)
问题来源：
http://www.lintcode.com/zh-cn/problem/largest-number/
思路：
两种思路：
一：
1、将vector内所有元素的所有位都分别按元素顺序保存在二维数组中；//O(Cn)
2、比较vecotr内所有元素的首位的大小，以样例为例，即比较1，2，2，4，8的大小，并排序记录其位置，排序可采用二叉排序；//时间复杂度为O(nlogn)
3、基于上一步，进行第二位排序，没有第二位的则不参与排序，记录排序后的位置；//时间复杂度为O(nlogn)
4、重复以上过程，直至不存在元素没有位参与排序；//总时间复杂度为O(nlogn)
5、基于已经记录的位置进行输出。
二：
1、找到vector所有元素的最大值，确认是否与int极限处于同一数量级，不处于则进行步骤2，处于则进行步骤3;//O(n)
2、如果最大值与int极限不处于同一数量级，则将其余所有数都提升到最大值所在数量级，然后直接二叉排序，记录其位置，并根据位置进行输出；//O(nlogn)
3、如果最大值与int极限处于同一数量级，则统计vector所有元素中该数量级的元素，并二叉排序，记录其位置；//O(nlogn)
4、将上一步骤排序后的元素除10，并顺序递减；//O(n)
5、将vector中其余元素提升到上一步骤的数量级，将所有元素排序，并记录其位置，并根据位置进行输出；//O(nlogn)
其实上面两种思路归结起来都可以算是同一种思路，都是将所有元素处于同一量级之后进行排序，但不同的点在于，一个是降量级操作，一个是升量级操作。
降量级操作因为需要元素的每一位都需要排序，所以相对的常数C会大一些。并且因为需要记录额外的元素位信息，空间复杂度也会相应大一些。
所以本文采用了升量级操作。升量级操作最值得注意的一点就是不可超过int极限，所以当存在元素与int极限处于同一量级时，首先需要对这些元素进行将量级操作，再将其余元素升量级。
Code:
1 class Solution { 2 public: 3 /* 4 * @param nums: A list of non negative integers 5 * @return: A string 6 */ 7 string largestNumber(vector<int> &nums) { 8 // write your code here 9 vector<int> order_nums = nums; 10 vector<int> sort_nums = nums; 11 vector<int> sitea = nums; 12 vector<int> siteb = nums; 13 vector<int> overnum, oversite; 14 int MaxN = nums.size(); 15 int IntMax = 1 << 31;//取得int极限 16 int NumMax = 0; 17 int Nlevel = 0; 18 int gain = 1; 19 int Ilevel = 0; 20 int Tmp = -1; 21 string out = ""; 22 if (MaxN <= 1) {//简单的异常与情况处理 23 if (MaxN){ 24 return to_string(nums[0]); 25 } 26 return ""; 27 } 28 for (int i = 0; i < MaxN; i++) {//寻找最大值，时间复杂度O(n) 29 sitea[i] = 0; 30 if (NumMax < nums[i]) { 31 NumMax = nums[i]; 32 } 33 }// O(n) 34 Tmp = NumMax / 10;//记录最大值的降量级值 35 if (!NumMax) {//简单情况处理 36 return "0"; 37 } 38 while (NumMax) {//获取最大值量级 39 Nlevel++; 40 NumMax /= 10; 41 }// O(c) 42 while(IntMax) {//获取int极限量级 43 Ilevel++; 44 IntMax /= 10; 45 } 46 if (Nlevel == Ilevel) {//最大值量级与int极限量级是否一致 47 gain *= pow(10, Nlevel - 2);//升量级后的最小值 48 for (int i = 0; i < MaxN; i++) {//获得所有与最大值量级处于同一量级的数 49 if(order_nums[i] >= gain) { 50 overnum.insert(overnum.end(), order_nums[i]); 51 oversite.insert(oversite.end(), i); 52 } 53 } 54 vector<int> oversort = overnum; 55 vector<int> sortsite = oversite; 56 vector<int> storesite = oversite; 57 twosort(oversort, overnum, sortsite, oversite, 0, overnum.size() - 1, (overnum.size() - 1) / 2);//将所有与最大量级处于同一量级的数排序并记录其位置 58 for (int i = 0; i < oversort.size(); i++) {//将所有与最大量级处于同一量级的数降量级操作 59 nums[storesite[i]] = oversort[i]; 60 order_nums[storesite[i]] = sort_nums[storesite[i]] = Tmp--; 61 } 62 } 63 else { 64 gain *= pow(10, Nlevel - 1);//升量级后的最小值 65 } 66 for (int i = 0; i < MaxN; i++) {//根据gain值进行升量级操作 67 siteb[i] = i; 68 order_nums[i] = gainnum(order_nums[i], gain, order_nums[i]); 69 //cout << order_nums[i] << " " << gain << endl; 70 }// O(cn) 71 twosort(order_nums, sort_nums, sitea, siteb, 0, MaxN - 1, (MaxN - 1) / 2);//将所有数进行排序并记录其位置 72 for (int i = 0 ;i < MaxN; i++) {//根据位置，将所有值输出 73 out += to_string(nums[sitea[i]]); 74 } 75 return out; 76 } 77 78 int gainnum(int num, const int gain,const int ori) {//升量级函数，根据传入的gain值判断是否num是否已经达到对应量级，并判断num为0的情况 79 if (num >= gain || !num) { 80 //cout << num << endl; 81 return num; 82 } 83 //cout << num << endl; 84 return gainnum(num * 10 + ori, gain, ori);//确保升量级操作后的num数为原初num数的1...1倍 85 } 86 87 int twosort(vector<int> &nums, vector<int> &sort, vector<int> &sitea, vector<int> &siteb, const int start, const int end, int mid) {//二叉排序算法，并同时记录位置 88 if (start >= end) {//当数组起始位置大于等于末尾位置时，可认为已排序 89 return 0; 90 } 91 int fr = start, bc = end, MidNum = nums[mid], tmp =start; 92 for (int i = start; i <= end; i++) { 93 if (nums[i] > MidNum) {//大则将值置于数组前段 94 sort[fr] = nums[i]; 95 sitea[fr] = siteb[i]; 96 fr++; 97 } 98 else if (nums[i] < MidNum) {//小则将值置于数组后段 99 sort[bc] = nums[i]; 100 sitea[bc] = siteb[i]; 101 bc--; 102 } 103 else {//等于则略过 104 continue; 105 } 106 }//O(n) 107 tmp = fr; 108 for(int i = start; i <= end; i++) {//将相等情况平行放入前段与后段的中间位置 109 if (nums[i] == MidNum) { 110 sort[tmp] = nums[i]; 111 sitea[tmp] = siteb[i]; 112 tmp++; 113 } 114 }//O(n) 115 if ((bc == end && tmp <= bc)) {//当所有元素都大于该数组最后一个值，且前段+相等情况的大小皆处于数组范围内时，可认为已经排序完成 116 nums = sort; 117 siteb = sitea; 118 return 0; 119 } 120 nums = sort; 121 siteb = sitea;//将数组和位置赋予另一数组和位置，以便下一轮排序 122 twosort(nums, sort, sitea, siteb, start, fr - 1, (start + fr - 1) / 2);//前段排序 123 twosort(nums, sort, sitea, siteb, tmp, end, (tmp + end) / 2);//后端排序 124 return 0; 125 }//O(nlogn) 126 };
贪心法：
本题是贪心法的一个很简单的题目应用，如采用第一种方法，则可以明显看到每一步都是在寻找当前位的最大值，直到到达峰顶（也就是不存在下一位的情况）。第二种方法虽然最多只有两步排序，但也采用了同样的思路：找到同一量级的最大值，然后排序输出。
二叉排序&指针：
二叉排序的思路主要就是将大于中间位置值的数往数组前/后段上排列，小于则往另一段上排列，存在多个与中间位置值相同的值时，则建议平行插入前后段已经确认的中间位置，不改变其顺序。
重复调用本身，即可完成整个数组的排列。
不过需要注意的时，函数传递参数时是传递该参数的一份拷贝，不是该参数本身，所以twosort要将排序好的值及其对应位置传递出来时，需要取其地址传入。
即：int twosort(vector<int> &nums, vector<int> &sort, vector<int> &sitea, vector<int> &siteb, const int start, const int end, int mid)
本文采用vector向量，不采用数组则是因为数组传递进去的是数组首地址，而要赋值的话，则不能直接进行siteb=sitea这样的赋值操作，这样只会将siteb的指针指向sitea的指针指向的位置，即&sitea[0]。
所以若要采用数组，又想对数组进行赋值，则需要使用for循环进行赋值，虽然时间复杂度在n的情况下，总体不变，但是代码就会冗余一些。
而采用vector向量则可以避免该问题，虽然twosort传入的也是vector向量的地址，但进行操作时，并不是针对地址进行操作，而只是值发生改变，并且vector向量可以进行(vector<int>) a = (vector<int>) b这样的操作，在代码上就会简洁清晰。
题目虽然不难，但是对贪心法和二叉排序的认知就因此上了一个步骤，不再只是看了看书和看了看代码的程度。
- 还没有人评论，欢迎说说您的想法！
客服
