题目

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

  1. Input: [10,2]
  2. Output: "210"

Example 2:

  1. Input: [3,30,34,5,9]
  2. Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

题意

给定一个数组，要求将其中所有数的顺序重新排列，使其能组成一个最大的数(字符串的形式)。

思路

对于整数a和b，如何确定哪个数放在前面，可以用如下方法：比较字符串ab和ba的字典序，若ab > ba则先放a，反之先放b。数组排好序后，将各元素依次拼接成字符串即为答案。如果排序后的数组第一个元素为0，说明后面所有元素都为0，只要返回0即可。

因为求的是最大数可以像上面这样简单处理，但如果求的是最小数则要进一步处理0的问题(因为0不能放在最大位上，这是无效的)，可以采取以下措施：1. 遍历一遍数组，统计0的个数为n，并将非零整数存入新数组中；2. 将新数组按照字典序进行排序；3. 在第一个元素后添加n个0。

代码实现

Java

  1. class Solution {
  2.     public String largestNumber(int[] nums) {
  3.         String[] strs = new String[nums.length];
  4.         for (int i = 0; i < nums.length; i++) {
  5.             strs[i] = String.valueOf(nums[i]);
  6.         }
  7.         Arrays.sort(strs, new Cmp());
  9.         // 都一个元素为0，说明后面所有元素都为0
  10.         if (strs[0].equals("0")) {
  11.             return "0";
  12.         }
  14.         StringBuilder ans = new StringBuilder();
  15.         for (int i = 0; i < strs.length; i++) {
  16.             ans.append(strs[i]);
  17.         }
  19.         return ans.toString();
  20.     }
  22.     private class Cmp implements Comparator<String> {
  23.         @Override
  24.         public int compare(String o1, String o2) {
  25.             return (o2 + o1).compareTo(o1 + o2);
  26.         }
  27.     }
  28. }

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {string}
  4.  */
  5. var largestNumber = function (nums) {
  6.   nums.sort((a, b) => (a + '' + b <= b + '' + a ? 1 : -1))
  8.   if (nums[0] === 0) {
  9.     return '0'
  10.   }
  12.   return nums.join('')
  13. }