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.
看到这道题的第一感觉就是须要进行排序，可是想了想，却没有什么合适的排序算法，有种感觉就是用跟基数排序类似的算法。或者自己直接修改基数排序
结果因为数据位数的不确定，没有实施成功。然后就百度了下
import java.util.*; public class LargestNumber{ public static void main(String[] args){ int[] num = {3232543,0,0,34350,34,12312329,86,5}; System.out.println("结果:" + getLargestNumber(num)); } private static String getLargestNumber(int[] num){ if(num.length < 1 ){ return ""; } String[] strs = new String[num.length]; for(int i = 0; i < num.length ; i ++){ strs[i] = String.valueOf(num[i]); } //依照数字在结果中的位置排序 Arrays.sort(strs,new Cmp()); for(int i = 0 ; i < num.length ; i ++){ System.out.print(strs[i] + ","); } System.out.println(); //把全部的字符串拼接在一起 String res = ""; for(int i = num.length - 1; i >= 0 ; i--){ res = res.concat(strs[i]); } //去掉数字开头的0，如输入[0,0] int i = 0; while(i < num.length && res.charAt(i) == 0){ i++; } if(i == num.length) return "0"; return res.substring(i); } } class Cmp implements Comparator<String>{ @Override public int compare(String a,String b){ String ab = a.concat(b); String ba = b.concat(a); return ab.compareTo(ba); } } 这个程序里最重要的是排序所用的比較器，这个比較器是自定义的，扩展：
Arrays.sort(T[], Comparator < ?
super T > c) 是用来对用户自己定义的对象数组排序功能的。Java 官方文档简单描写叙述了它的作用，但不足以让我们深刻理解。为了更深入地理解它，这篇文章将梳理相关的关键点。
1、简单实例：怎样使用Arrays.sort()
通过阅读以下代码。你能高速正确了解这种方法的用途。
Comparator（比較器）用于依据Dogs的size比較其大小，并作为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 39 import java.util.Arrays; import java.util.Comparator; class Dog{ int size; public Dog( int s){ size = s; } } class DogSizeComparator implements Comparator<Dog>{ @Override public int compare(Dog o1, Dog o2) { return o1.size - o2.size; } } public class ArraySort { public static void main(String[] args) { Dog d1 = new Dog( 2 ); Dog d2 = new Dog( 1 ); Dog d3 = new Dog( 3 ); Dog[] dogArray = {d1, d2, d3}; printDogs(dogArray); Arrays.sort(dogArray, new DogSizeComparator()); printDogs(dogArray); } public static void printDogs(Dog[] dogs){ for (Dog d: dogs) System.out.print(d.size + " " ); System.out.println(); } } 输出： 1 2 2 1 3 1 2 32、策略模式的使用
这是运用策略模式的一个非常好的场景，为什么策略模式对于这样的场景非常适用？简单来说。策略模式使不同的算法在执行时得以选择。在这个样例中，通过传递不同的Comparator。能够选择不同的算法。
基于上例，如今如果你有一个Comparator，用weight来取代size来比較Dogs。
你能够简单创建一个新的Comprator例如以下：
class Dog{ int size; int weight; public Dog( int s, int w){ size = s; weight = w; } } class DogSizeComparator implements Comparator<Dog>{ @Override public int compare(Dog o1, Dog o2) { return o1.size - o2.size; } } class DogWeightComparator implements Comparator<Dog>{ @Override public int compare(Dog o1, Dog o2) { return o1.weight - o2.weight; } } public class ArraySort { public static void main(String[] args) { Dog d1 = new Dog( 2 , 50 ); Dog d2 = new Dog( 1 , 30 ); Dog d3 = new Dog( 3 , 40 ); Dog[] dogArray = {d1, d2, d3}; printDogs(dogArray); Arrays.sort(dogArray, new DogSizeComparator()); printDogs(dogArray); Arrays.sort(dogArray, new DogWeightComparator()); printDogs(dogArray); } public static void printDogs(Dog[] dogs){ for (Dog d: dogs) System.out.print( "size=" +d.size + " weight=" + d.weight + " " ); System.out.println(); } }输出：
1 2 3 size= 2 weight= 50 size= 1 weight= 30 size= 3 weight= 40 size= 1 weight= 30 size= 2 weight= 50 size= 3 weight= 40 size= 1 weight= 30 size= 3 weight= 40 size= 2 weight= 50Comparator不过一个接口。不论什么实现了Comparator在执行时都能够被使用，这是策略模式的核心理念。
3、为什么使用“super”
非常显然。假设”Comparator<T>c”作为參数，可是第二个參数是”Comparator< ? super T > c”，使用<?
super T>意味着类型能够是T或者是它的超类。为什么同意超类型呢？答案是：这样的方式同意全部子类使用同一个comparator。看看以下这个样例一目了然。
import java.util.Arrays; import java.util.Comparator; class Animal{ int size; } class Dog extends Animal{ public Dog( int s){ size = s; } } class Cat extends Animal{ public Cat( int s){ size = s; } } class AnimalSizeComparator implements Comparator<Animal>{ @Override public int compare(Animal o1, Animal o2) { return o1.size - o2.size; } //in this way, all sub classes of Animal can use this comparator. } public class ArraySort { public static void main(String[] args) { Dog d1 = new Dog( 2 ); Dog d2 = new Dog( 1 ); Dog d3 = new Dog( 3 ); Dog[] dogArray = {d1, d2, d3}; printDogs(dogArray); Arrays.sort(dogArray, new AnimalSizeComparator()); printDogs(dogArray); System.out.println(); //when you have an array of Cat, same Comparator can be used. Cat c1 = new Cat( 2 ); Cat c2 = new Cat( 1 ); Cat c3 = new Cat( 3 ); Cat[] catArray = {c1, c2, c3}; printDogs(catArray); Arrays.sort(catArray, new AnimalSizeComparator()); printDogs(catArray); } public static void printDogs(Animal[] animals){ for (Animal a: animals) System.out.print( "size=" +a.size + " " ); System.out.println(); } } 输出： 1 2 3 4 5 size= 2 size= 1 size= 3 size= 1 size= 2 size= 3 size= 2 size= 1 size= 3 size= 1 size= 2 size= 34、总结
总的来说。从Arrays.sort()中你应该了解到：
generic(范型)——super策略模式归并排序——nlog(n)时间复杂度 java.util.Collections.sort(List<T>list, Comparator<?super T> c)类似于Arrays.sort參考：Arrays.sort(T[], java.util.Comparator)
版权声明：本文博主原创文章。博客，未经同意不得转载。
转载于:https://www.cnblogs.com/bhlsheji/p/4811553.html
相关资源：数据结构—成绩单生成器