本文共 2055 字，大约阅读时间需要 6 分钟。

链接：

大意：

给定一个整型数组nums，nums中每个元素都是非负数。要求对nums中各个元素进行一个组合，使得该组合后的数是所有组合得到的结果中最大的。例子：

思路：

可以使用基于交换的冒泡排序算法，记录字符串 s1 = "" + nums[i] + nums[i + 1]，s2 = "" + nums[i + 1] + nums[i]。如果s2比s1大，则需要交换nums[i]和nums[i + 1]的位置。

最后，先判断nums[0]的数字大小：如果是0，则直接返回"0"。否则依次将nums中的元素append到StringBuilder对象sb中，最后返回sb.toString()。

代码：

class Solution {    public String largestNumber(int[] nums) {        boolean end = false; //标志冒泡排序是否提前结束        // 基于冒泡排序        for (int i = 0; i < nums.length; i++) {            end = true;            for (int j = 0; j < nums.length - i - 1; j++) {                String s1 = "" + nums[j] + nums[j + 1], s2 = "" + nums[j + 1] + nums[j];                // 只有当s2比s1大时 才交换两个字符串位置                if (s1.compareTo(s2) < 0) {                    end = false;                    int t = nums[j];                    nums[j] = nums[j + 1];                    nums[j + 1] = t;                }            }            if (end)                break;        }        // 如果经过排序后的第一个数字是0 那么直接返回"0"        if (nums[0] == 0)            return "0";        StringBuilder sb = new StringBuilder();        for (int i = 0; i < nums.length; i++) {            sb.append(nums[i]);        }        return sb.toString();    }}

结果：

结论：

效率有点低，可能是冒泡排序效率低的原因。想了下，为什么不直接用内置的排序函数？（基于快排实现的）。需要改进。。

改进：

class Solution {    public String largestNumber(int[] nums) {        // 将基本数据类型转为引用数据类型  Comparator不支持自定义基本数据类型排序        Integer[] numss = new Integer[nums.length];        for (int i = 0; i < nums.length; i++) {            numss[i] = nums[i];        }        // 使用内置排序Arrays.sort(nums) 基于快速排序        Arrays.sort(numss, new Comparator
   
    (){            public int compare(Integer i1, Integer i2) {                String s1 = "" + i1 + i2, s2 = "" + i2 + i1;                return s2.compareTo(s1);            }        });        // 如果经过排序后的第一个数字是0 那么直接返回"0"        if (numss[0] == 0)            return "0";        StringBuilder sb = new StringBuilder();        for (int i = 0; i < numss.length; i++) {            sb.append(numss[i]);        }        return sb.toString();    }}
   

转载地址：http://zaesi.baihongyu.com/