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.
1
我的想法是排序，然后按顺序输出即可。关键在于如何排定两个元素的顺序。可以这么做： 比如 86 76 ，那么就比较7686 8676的大小即可。 代码里实现了快排，我尽量会少用java的语言特性，加强自己的基本功训练。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public String largestNumber(int[] nums){
if(nums == null || nums.length == 0) return "0";
int allZero = 0;
for(int i = 0; i < nums.length; i++){
if(nums[i]==0)
allZero++;
}
if(allZero == nums.length) return "0";
quickSort(nums,0,nums.length-1);
StringBuilder sb = new StringBuilder();
for(int i = 0; i < nums.length; i++){
sb.append(nums[i]);
}
return sb.toString();
}
private void quickSort(int[] nums,int lo,int hi){
if(nums == null || nums.length < 1) return;
if(lo >= hi) return;
int j = partition(nums,lo,hi);
quickSort(nums,lo,j-1);
quickSort(nums,j+1,hi);
}
private void swap(int[] nums,int i, int j){
if(i == j) return;
if(nums[i] == nums[j]) return;
nums[i] ^= nums[j];
nums[j] ^= nums[i];
nums[i] ^= nums[j];
}
private boolean bigger(int[] nums, int i, int j){
if(nums[i] == 0) return false;
if(nums[j] == 0) return true;
int idigits = 0;
int jdigits = 0;
long a = nums[i];
long b = nums[j];
while(a != 0){
a = a / 10;
idigits++;
}
while(b != 0){
b = b / 10;
jdigits++;
}
a = nums[i];
b = nums[j];
for(int k = 0; k < jdigits; k++){
a = 10;
}
for(int k = 0; k < idigits; k++){
b = 10;
}
return (a+nums[j]) > (b+nums[i]);
<span class="o">}</span>
<span class="kd">private</span> <span class="kt">int</span> <span class="nf">partition</span><span class="o">(</span><span class="kt">int</span><span class="o">[]</span> <span class="n">nums</span><span class="o">,</span><span class="kt">int</span> <span class="n">lo</span><span class="o">,</span> <span class="kt">int</span> <span class="n">hi</span><span class="o">){</span>
<span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="n">lo</span><span class="o">;</span>
<span class="kt">int</span> <span class="n">j</span> <span class="o">=</span> <span class="n">hi</span><span class="o">+</span><span class="mi">1</span><span class="o">;</span>
<span class="k">while</span><span class="o">(</span><span class="kc">true</span><span class="o">){</span>
<span class="k">while</span><span class="o">(</span><span class="n">bigger</span><span class="o">(</span><span class="n">nums</span><span class="o">,++</span><span class="n">i</span><span class="o">,</span><span class="n">lo</span><span class="o">))</span> <span class="k">if</span><span class="o">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">hi</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
<span class="k">while</span><span class="o">(</span><span class="n">bigger</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">lo</span><span class="o">,--</span><span class="n">j</span><span class="o">))</span> <span class="k">if</span><span class="o">(</span><span class="n">j</span> <span class="o">==</span> <span class="n">lo</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
<span class="k">if</span><span class="o">(</span><span class="n">i</span> <span class="o">>=</span> <span class="n">j</span><span class="o">)</span> <span class="k">break</span><span class="o">;</span>
<span class="n">swap</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">i</span><span class="o">,</span><span class="n">j</span><span class="o">);</span>
<span class="o">}</span>
<span class="n">swap</span><span class="o">(</span><span class="n">nums</span><span class="o">,</span><span class="n">lo</span><span class="o">,</span><span class="n">j</span><span class="o">);</span>
<span class="k">return</span> <span class="n">j</span><span class="o">;</span>
<span class="o">}</span><span class="w">
2 most votes
思路也和我的一样，排序，排序的比较方法，输出。
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public String largestNumber(int[] num) {
if(num==null || num.length==0)
return "";
String[] Snum = new String[num.length];
for(int i=0;i<num.length;i++)
Snum[i] = num[i]+"";
<span class="n">Comparator</span><span class="o"><</span><span class="n">String</span><span class="o">></span> <span class="n">comp</span> <span class="o">=</span> <span class="k">new</span> <span class="n">Comparator</span><span class="o"><</span><span class="n">String</span><span class="o">>(){</span>
<span class="nd">@Override</span>
<span class="kd">public</span> <span class="kt">int</span> <span class="nf">compare</span><span class="o">(</span><span class="n">String</span> <span class="n">str1</span><span class="o">,</span> <span class="n">String</span> <span class="n">str2</span><span class="o">){</span>
<span class="n">String</span> <span class="n">s1</span> <span class="o">=</span> <span class="n">str1</span><span class="o">+</span><span class="n">str2</span><span class="o">;</span>
<span class="n">String</span> <span class="n">s2</span> <span class="o">=</span> <span class="n">str2</span><span class="o">+</span><span class="n">str1</span><span class="o">;</span>
<span class="k">return</span> <span class="n">s1</span><span class="o">.</span><span class="na">compareTo</span><span class="o">(</span><span class="n">s2</span><span class="o">);</span>
<span class="o">}</span>
<span class="o">};</span>
<span class="n">Arrays</span><span class="o">.</span><span class="na">sort</span><span class="o">(</span><span class="n">Snum</span><span class="o">,</span><span class="n">comp</span><span class="o">);</span>
<span class="k">if</span><span class="o">(</span><span class="n">Snum</span><span class="o">[</span><span class="n">Snum</span><span class="o">.</span><span class="na">length</span><span class="o">-</span><span class="mi">1</span><span class="o">].</span><span class="na">charAt</span><span class="o">(</span><span class="mi">0</span><span class="o">)==</span><span class="sc">'0'</span><span class="o">)</span>
<span class="k">return</span> <span class="s">"0"</span><span class="o">;</span>
<span class="n">StringBuilder</span> <span class="n">sb</span> <span class="o">=</span> <span class="k">new</span> <span class="n">StringBuilder</span><span class="o">();</span>
<span class="k">for</span><span class="o">(</span><span class="n">String</span> <span class="nl">s:</span> <span class="n">Snum</span><span class="o">)</span>
<span class="n">sb</span><span class="o">.</span><span class="na">insert</span><span class="o">(</span><span class="mi">0</span><span class="o">,</span> <span class="n">s</span><span class="o">);</span>
<span class="k">return</span> <span class="n">sb</span><span class="o">.</span><span class="na">toString</span><span class="o">();</span>