LeetCode刷题实战179：最大数 / 四六文摘

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大数 ，我们先来看题面：

https://leetcode-cn.com/problems/largest-number/

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

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

题意

给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

解题

组成最大数应使得高位数字尽量大，所以首先按照高位数字从大到小对数组排序，然后一次从高位到低位组成最大数。注意若数组全为0，则直接返回一个0. 另外要注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

class Solution {
    public String largestNumber(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            for(int j = 0; j < nums.length - i - 1; j++){
                String s1 = nums[j] + "" + nums[j + 1];
                String s2 = nums[j + 1] + "" + nums[j];
                if(s1.compareTo(s2) < 0){
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        String res = "";
        for(int i = 0; i < nums.length; i++){
            res += nums[i];
        }
        if(res.charAt(0) == '0'){
            return "0";
        }
        return res;
    }
}