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

解法分析

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

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进行排序。

解题代码

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);
	}
}