LeetCode 179. Largest Number

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2016/11/08/LeetCode-179-Largest-Number/

访问原文「LeetCode 179. Largest Number

题目要求

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.

题意解析

给出一个非负整型列表,对列表里的整型进行排序,使得排序后将这些数字连在一起的数字最大。

例如,非负整型列表为[3, 30, 34, 5, 9],排序后最大的值为9534330

注意:结果可能是一个非常大的值,所以用string代替integer

解法分析

这道题的排序方式为假设有两个数AB,如果AB>BA则排序为AB,否则排序为BA
java中有一个接口为Comparable,如下。

1
2
3
4
5
6
7
8
public interface Comparable<T> {
/**
* Compares this object with the specified object for order. Returns a
* negative integer, zero, or a positive integer as this object is less
* than, equal to, or greater than the specified object.
* ...
*/
public int compareTo(T o);

新建一个类只要实现了这个接口中的compareTo函数,就可以使用Arrays.sort进行排序。

解题代码

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
public String largestNumber(int[] nums) {
List<IntegerShadow> integerShadows = new ArrayList<IntegerShadow>();
for (int num : nums) {
if (num == 0) {
integerShadows.add(new IntegerShadow(0, "0"));
continue;
}
integerShadows.add(new IntegerShadow(num, String.valueOf(num)));
}
IntegerShadow[] integerShadows2 = new IntegerShadow[integerShadows
.size()];
integerShadows.toArray(integerShadows2);
Arrays.sort(integerShadows2);
StringBuilder sb = new StringBuilder();
for (int i = integerShadows2.length - 1; i >= 0; i--) {
sb.append(integerShadows2[i].ori);
}
if (sb.toString().matches("0+")) {
return "0";
} else {
return sb.toString();
}
}
class IntegerShadow implements Comparable<IntegerShadow> {
public int ori;
public String oriStr;
public IntegerShadow(int o, String s) {
this.ori = o;
this.oriStr = s;
}
@Override
public int compareTo(IntegerShadow o) {
return (this.oriStr + o.oriStr).compareTo(o.oriStr + this.oriStr);
}
}
Jerky Lu wechat
欢迎加入微信公众号