题目描述（中等难度）

给一个数组，将这些数任意排列，组成一个值最大的数。

解法一

直觉上，我们应该先选最高位大的数。有 开头的数字先选 9，然后选 8 开头的数，再选 7 开头的… 以此类推。所以我们需要一个函数来判断最高位是多少。

举个例子，比如对于 5,914,67，先选 914，再选 67，再选 5，组成 914675，因为数字的高位越大越好，每次尽量选高位的大的数从而保证了最后构成的数一定是最大的。

接下来的一个问题，如果最高位的数字一样呢？又分成两种情况。

如果两个数字长度相等，比如 34 和 30 ， 那么很明显，选择较大的即可。

如果两个数字长度不相等，比如 3 和 30，此时先选择 3 还是先选择 30 呢？

我们只需要把它两拼接在一起直接去比较，也就是比较 330 和 303，很明显是 330 大，所以我们先选择 3。

所以我们可以封装一个比较函数。

  1. private int compare(int n1, int n2) {
  2.     int len1 = (n1 + "").length();
  3.     int len2 = (n2 + "").length();
  4.     //长度相等的情况
  5.     if (len1 == len2) {
  6.         if (n1 > n2) {
  7.             return 1;
  8.         } else if (n1 < n2) {
  9.             return -1;
  10.         } else {
  11.             return 0;
  12.         }
  13.     }
  14.     //长度不等的情况
  15.     int combination1 = (int) (n1 * Math.pow(10, len2)) + n2;
  16.     int combination2 =(int) (n2 * Math.pow(10, len1)) + n1;
  18.     if (combination1 > combination2) {
  19.         return 1;
  20.     } else if (combination1 < combination2) {
  21.         return -1;
  23.         return 0;
  24.     }
  25. }

所以我们还需要一个插入元素到链表的方法。对于链表，我们的头结点不去存储值，而 head.next 才是我们第一个存储的值。

然后对于 3,30,34,5,9，我们就会有下边的结构。

  1. 9: head -> 9
  2. 8:
  3. 7:
  4. 6: 
  5. 5: head -> 5
  6. 4:
  7. 3: head -> 34 -> 3 -> 30
  8. 2:
  9. 1:
  10. 0:

然后我们只需要依次遍历这些数字组成一个字符串即可，即9534330。

然后把上边所有的代码合起来即可。

解法二

仔细想一下上边的想法，我们通过每个数字的最高位人为的把所有数字分成 10 类，然后每一类做了一个插入排序。其实我们也可以不进行分类，直接对所有数字进行排序。

我们直接调用系统的排序方法，传一个我们自定义的比较器即可。看一下我们之前的比较函数是否可以用。

  1. private int compare(int n1, int n2) {
  2.     int len1 = (n1 + "").length();
  3.     int len2 = (n2 + "").length();
  4.     if (len1 == len2) {
  5.         if (n1 > n2) {
  6.             return 1;
  7.         } else if (n1 < n2) {
  8.             return -1;
  9.         } else {
  10.             return 0;
  11.         }
  12.     }
  13.     int combination1 = (int) (n1 * Math.pow(10, len2)) + n2;
  14.     int combination2 = (int) (n2 * Math.pow(10, len1)) + n1;
  16.     if (combination1 > combination2) {
  17.         return 1;
  18.         return -1;
  19.     } else {
  20.         return 0;
  21.     }
  23. }

之前我们只考虑了最高位相等的情况，如果最高位不同的话检查一下上边的代码是否还可以用。比如对于 93,234，然后根据上边代码我们会比较 93234 和 23493，然后我们会选择 93，发现代码不需要修改。

此外，因为我们要从大到小排列，所以前一个数字大于后一个数字的时候，我们应该返回 -1。

解法三

上边的解法严格来说其实还是有些问题的。在比较两个数字大小的时候，当长度不相等的时候，我们把两个数字合并起来。如果数字特别大，强行把它们合并起来是会溢出的。

所以我们可以把数字转为 String ，把字符串合并起来，然后对字符串进行比较。

此外，在比较函数中我们单独分别判断了数字长度相等和不相等的情况，其实长度相等的情况也是可以合并到长度不相等的情况中去的。

  1. public String largestNumber(int[] nums) {
  2.     Integer[] n = new Integer[nums.length];
  3.     for (int i = 0; i < nums.length; i++) {
  4.         n[i] = nums[i];
  5.     }
  6.     Arrays.sort(n, new Comparator<Integer>() {
  7.         @Override
  8.         public int compare(Integer n1, Integer n2) {
  9.             String s1 = n1 + "" + n2;
  10.             String s2 = n2 + "" + n1;
  11.             //compareTo 方法
  12.             //如果参数是一个按字典顺序排列等于该字符串的字符串，则返回值为0; 
  13.             //如果参数是按字典顺序大于此字符串的字符串，则返回值小于0; 
  14.             //如果参数是按字典顺序小于此字符串的字符串，则返回值大于0。
  15.             return s2.compareTo(s1);
  16.         }
  17.     });
  18.     StringBuilder sb = new StringBuilder();
  19.     for (int i = 0; i < nums.length; i++) {
  20.         sb.append(n[i]);
  21.     }
  22.     String res = sb.toString();

总

只要找到了选取数字的原则，这道题也就转换成一道排序题了。

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情