[Leetcode] Largest Number 最大整數

wuyumin 發布于2019-08-14 12:40 / 1563人閱讀

摘要：拼接比較法復雜度時間空間思路要拼成最大數，我們只要讓較大的數排在前面，較小的數排在后面就行。注意如果排序后第一個數是，則直接返回，因為后面的數只有可能是了。

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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