Largest Number

Description：

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.

Code：

 1  int islesseq(int&a, int&b)
 2     {
 3         stringstream ss;
 4         string strA, strB;
 5         
 6         ss << a;
 7         ss >> strA;
 8         ss.clear();
 9         ss << b;
10         ss >> strB;
11         
12         if (strA+strB <= strB+strA)
13         {
14             return 1;
15         }
16         else
17             return 0;
18     }
19     
20     int partition(vector<int>&nums, int low, int high)
21     {
22         int key = nums[low];
23         while (low<high)
24         {
25             while (low < high && islesseq(key,nums[high]))--high;
26             nums[low] = nums[high];
27             while (low < high && islesseq(nums[low],key))++low;
28             nums[high] = nums[low];
29         }
30         nums[low] = key;
31         return low;
32     }
33     
34     void sort(vector<int>&nums, int low, int high)
35     {
36         if (low < high)
37         {
38             int pivot = partition(nums,low, high);
39             sort(nums,low,pivot-1);
40             sort(nums, pivot+1, high);
41         }
42     }
43     
44     string largestNumber(vector<int>& nums) {
45         sort(nums,0, nums.size()-1);
46         if (nums[nums.size()-1] == 0)
47             return "0";
48         stringstream ss;
49         for (int i = nums.size()-1; i >= 0; --i)
50         {
51             ss<<nums[i];
52         }
53         return ss.str();
54     }

View Code