LeetCode_排序_中等_179.最大数-蒲公英云

LeetCode_排序_中等_179.最大数

1.题目

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：
输入：nums = [10,2]
输出：“210”

示例 2：
输入：nums = [3,30,34,5,9]
输出：“9534330”

示例 3：
输入：nums = [1]
输出：“1”

示例 4：
输入：nums = [10]
输出：“10”

提示：
1 <= nums.length <= 100
0 <= nums[i] <= 109

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-number

2.思路

（1）简单交换排序
利用简单交换排序的思想对数组元素进行排序，不过排序的规则所有变化，先将要排序的两个数 nums[i] 和 nums[j] 转换为字符串 a 和b，然后用函数 compareTo() 比较 a + b 与 b + a 的大小，a + b == b + a 返回 0，a + b > b + a 返回正数，a + b < b + a 返回负数。由于简单交换排序的特点，即每完成一趟排序，就至少会有一个元素的位置确定，所以可以在排序的同时对结果进行字符串的拼接。

3.代码实现（Java）

//思路1————简单交换排序
public String largestNumber(int[] nums) {
    int length = nums.length;
    if (length == 1) {
        return Integer.toString(nums[0]);
    }
    int tmp;
    String res = "";
    for (int i = 0; i < length; i++) {
        for (int j = i + 1; j < length; j++) {
            String a = Integer.toString(nums[i]);
            String b = Integer.toString(nums[j]);
            if ((a + b).compareTo(b + a) < 0) {
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
        }
        //如果排序后的第一个元素是0，那其后面的元素肯定均为 0（因为 nums 中的值均为非负整数），直接返回 0 即可
        if (nums[0] == 0) {
            return "0";
        }
        res += Integer.toString(nums[i]);
    }
    return res;
}