[Leetcode] Largest Number 最大整数

wuyumin 发布于2019-08-14 12:40 / 1527人阅读

摘要：拼接比较法复杂度时间空间思路要拼成最大数，我们只要让较大的数排在前面，较小的数排在后面就行。注意如果排序后第一个数是，则直接返回，因为后面的数只有可能是了。

Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string
instead of an integer.

拼接比较法 复杂度

时间 O(NlogN) 空间 O(N)

思路

要拼成最大数，我们只要让较大的数排在前面，较小的数排在后面就行。然而如何对原数组排序呢？当比较一位数时，直接比较大小就行了，但对于多位数呢？

从第一位向后比较，如果有一位更大，则该数更大，如9大于15，24大于23。

如果某个数的前半部分和另一个数完全相同，则看该数剩下的那部分和另一个数的大小关系，如2332和23比较时，2332是大于23的，因为32大于23。
不过如果细分各种情况，会弄得非常复杂，这里有个技巧，就是我们把两个数拼在一起，然后再把这两个数换个顺序再拼在一起，这时候就可以直接比较了。比如2332和23，变成233223和232332两个数，这时候那个数更大，就说明这个数前半部分的那个数是更大的，这里是2332。

注意

如果排序后第一个数是0，则直接返回0，因为后面的数只有可能是0了。

代码

public class Solution {
    public String largestNumber(int[] nums) {
        Integer[] ints = new Integer[nums.length];
        // 将其放入Integer数组方便排序
        for(int i = 0; i < nums.length; i++){
            ints[i] = nums[i];
        }
        // 排序的方法是前后相拼再后前相拼，比较大小
        Arrays.sort(ints, new Comparator(){
            public int compare(Integer n1, Integer n2){
                System.out.println(n1 +":"+n2);
                String str1 = String.valueOf(n1);
                String str2 = String.valueOf(n2);
                return (str2 + str1).compareTo(str1 + str2);
            }
        });
        // 如果第一个数是0，则直接返回0
        if(ints[0] == 0){
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        // 将数从大到小拼起来就行了
        for(int i = 0; i < nums.length; i++){
            sb.append(ints[i]);
        }
        return sb.toString();
    }
}

GPU云服务器云服务器 Largest LeetCode LeetCode_String leetcode_35_SearchIn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64635.html

leetcode152 Maximum Product Subarray

摘要：题目要求从一个整数数组中找到一个子数组，该子数组中的所有元素的乘积最大。比如数组的最大乘积子数组为思路与代码这题目考察了动态编程的思想。至于为什么还要比较，是因为如果是一个负数的，那么之前的最小乘积在这里可能就成为了最大的乘积了。题目要求 Find the contiguous subarray within an array (containing at least one num...

Arno 2019-08-16 10:57 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
leetcode410. Split Array Largest Sum

摘要：在这里，边界被设置为该数组中可以得到的子数组元素和的最小值和最大值。在确定了数组元素和的上界和下界之后，就需要找出一种方法，来不断压缩区间直到最后一种。可以使用中间位置作为数组元素和的边界，即假设所有的连续数组的和都不会超过值。题目要求 Given an array which consists of non-negative integers and an integer m, y...

Jonathan Shieber 2019-08-16 17:31 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
LeetCode[333] Largest BST Subtree

摘要：复杂度思路考虑对于每一个节点来说，能组成的的。那么并且所以我们需要两个返回值，一个是这个是不是，另一个是当前的能组成的最大的值。代码这个能构成一个这个不能构成一个 LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

WrBug 2019-08-14 15:03 评论0 收藏0