最大数

179. 最大数

难度中等557

给定一组非负整数 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

通过次数65,138

提交次数167,258

在真实的面试中遇到过这道题？

将两个数合并在一起，比较A+B和B+A的大小

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.toString(nums[i]);
        }
        Arrays.sort(arr, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1 = o1 + o2;
                String s2 = o2 + o1;
                return s2.compareTo(s1);
            }
        });

        StringBuilder bd = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (bd.length()>0&&bd.charAt(0) == '0' && arr[i].equals("0")) continue;
            bd.append(arr[i]);
            
        }

        return bd.toString();
    }
}

##　官方题解java代码无法通过所有测试用例

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        // 转换成包装类型，以便传入 Comparator 对象（此处为 lambda 表达式）
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i < n; i++) {
            numsArr[i] = nums[i];
        }

        Arrays.sort(numsArr, (x, y) -> {
            long sx = 10, sy = 10;
            while (sx <= x) {
                sx *= 10;
            }
            while (sy <= y) {
                sy *= 10;
            }
            return (int) (-sy * x - y + sx * y + x);
        });

        if (numsArr[0] == 0) {
            return "0";
        }
        StringBuilder ret = new StringBuilder();
        for (int num : numsArr) {
            ret.append(num);
        }
        return ret.toString();
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/largest-number/solution/zui-da-shu-by-leetcode-solution-sid5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    
// 这个测试用例无法通过
[367668180, 394149547, 82622903, 110484543, 951791508, 624342624, 716422494, 886411575, 995036094, 779313232, 804553674, 569416650, 443965436, 258958825, 401183053, 257352374, 491348526, 406974617, 242280810, 272124759, 582624695, 82306379, 831614069, 911064485, 118364708, 500698241, 927727688, 873039797, 467297001, 816031731, 847227192, 442974087, 527049522, 279621058, 271817716, 160493859, 46930528, 382369865, 44234514, 345837908, 467861996, 22944598, 2788683, 396655486, 408456151, 338663600, 588558884, 440048504, 239313358, 311235345, 169422536, 161894055, 34503676, 590622333, 304991452, 513997357, 597694500, 50289888, 123424220, 830200592, 10791477, 10420737, 729213477, 966836660, 492389415, 888202834, 300138075, 339970820, 812182689, 635683955, 336611363, 90835006, 417108800, 252742854, 654713205, 158051302, 249037437, 856420153, 87665298, 792426959, 631482674, 342179099, 746289310, 962720332, 852925376, 46012189, 956251262, 189861234, 342691263, 327998473, 13136569, 526301748, 414906606, 714504434, 77814904, 446064254, 874970313, 880641847, 215764588, 569548985] 

赏

谢谢你请我吃糖果

微信