成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Leetcode] Largest Number 最大整數(shù)

wuyumin / 1572人閱讀

摘要：拼接比較法復(fù)雜度時(shí)間空間思路要拼成最大數(shù)，我們只要讓較大的數(shù)排在前面，較小的數(shù)排在后面就行。注意如果排序后第一個(gè)數(shù)是，則直接返回，因?yàn)楹竺娴臄?shù)只有可能是了。

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.
拼接比較法 復(fù)雜度

時(shí)間 O(NlogN) 空間 O(N)

思路

要拼成最大數(shù)，我們只要讓較大的數(shù)排在前面，較小的數(shù)排在后面就行。然而如何對(duì)原數(shù)組排序呢？當(dāng)比較一位數(shù)時(shí)，直接比較大小就行了，但對(duì)于多位數(shù)呢？

從第一位向后比較，如果有一位更大，則該數(shù)更大，如9大于15，24大于23。

如果某個(gè)數(shù)的前半部分和另一個(gè)數(shù)完全相同，則看該數(shù)剩下的那部分和另一個(gè)數(shù)的大小關(guān)系，如2332和23比較時(shí)，2332是大于23的，因?yàn)?2大于23。
不過如果細(xì)分各種情況，會(huì)弄得非常復(fù)雜，這里有個(gè)技巧，就是我們把兩個(gè)數(shù)拼在一起，然后再把這兩個(gè)數(shù)換個(gè)順序再拼在一起，這時(shí)候就可以直接比較了。比如2332和23，變成233223和232332兩個(gè)數(shù)，這時(shí)候那個(gè)數(shù)更大，就說明這個(gè)數(shù)前半部分的那個(gè)數(shù)是更大的，這里是2332。

注意

如果排序后第一個(gè)數(shù)是0，則直接返回0，因?yàn)楹竺娴臄?shù)只有可能是0了。

代碼 
public class Solution {
    public String largestNumber(int[] nums) {
        Integer[] ints = new Integer[nums.length];
        // 將其放入Integer數(shù)組方便排序
        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);
            }
        });
        // 如果第一個(gè)數(shù)是0，則直接返回0
        if(ints[0] == 0){
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        // 將數(shù)從大到小拼起來(lái)就行了
        for(int i = 0; i < nums.length; i++){
            sb.append(ints[i]);
        }
        return sb.toString();
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64635.html

相關(guān)文章

  • leetcode152 Maximum Product Subarray

    摘要：題目要求從一個(gè)整數(shù)數(shù)組中找到一個(gè)子數(shù)組，該子數(shù)組中的所有元素的乘積最大。比如數(shù)組的最大乘積子數(shù)組為思路與代碼這題目考察了動(dòng)態(tài)編程的思想。至于為什么還要比較，是因?yàn)槿绻且粋€(gè)負(fù)數(shù)的，那么之前的最小乘積在這里可能就成為了最大的乘積了。 題目要求 Find the contiguous subarray within an array (containing at least one num...

    Arno 評(píng)論0 收藏0

  • LeetCode 精選TOP面試題【51 ~ 100】

    摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...

    Clect 評(píng)論0 收藏0

  • leetcode410. Split Array Largest Sum

    摘要：在這里，邊界被設(shè)置為該數(shù)組中可以得到的子數(shù)組元素和的最小值和最大值。在確定了數(shù)組元素和的上界和下界之后，就需要找出一種方法，來(lái)不斷壓縮區(qū)間直到最后一種?？梢允褂弥虚g位置作為數(shù)組元素和的邊界，即假設(shè)所有的連續(xù)數(shù)組的和都不會(huì)超過值。 題目要求 Given an array which consists of non-negative integers and an integer m, y...

    Jonathan Shieber 評(píng)論0 收藏0

  • 前端 | 每天一個(gè) LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...

    張漢慶 評(píng)論0 收藏0

  • LeetCode[333] Largest BST Subtree

    摘要：復(fù)雜度思路考慮對(duì)于每一個(gè)節(jié)點(diǎn)來(lái)說，能組成的的。那么并且所以我們需要兩個(gè)返回值，一個(gè)是這個(gè)是不是，另一個(gè)是當(dāng)前的能組成的最大的值。代碼這個(gè)能構(gòu)成一個(gè)這個(gè)不能構(gòu)成一個(gè) LeetCode[333] Largest BST Subtree Given a binary tree, find the largest subtree which is a Binary SearchTree (B...

    WrBug 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<