給出一組非負整數，重新排列他們的順序把他們組成一個最大的整數。

VincentFF 發布于2019-07-30 16:09 / 3911人閱讀

摘要：文章為原創首發地址描述給出一組非負整數，重新排列他們的順序把他們組成一個最大的整數。算法每個元素逐個字符進行對比。代碼代碼測試以上代碼已放到的上開源，歡迎或提建議。運行即可以測試。

文章為原創首發地址：https://hooyes.net/p/python-l...

描述

給出一組非負整數，重新排列他們的順序把他們組成一個最大的整數。

例
給出 [1, 20, 23, 4, 8]，返回組合最大的整數應為 8423201
給出 [1, 201, 20, 9, 8]，返回組合最大的整數應為 98202011
給出 [1, 203, 20, 9, 8]，返回組合最大的整數應為 98203201

算法

我給簡單好理解的兩個排序算法：

算法1：

先把對比的數字轉成字符，拼接后再轉成整數進行大小對比，即 int(a+b) 與 int(b+a) 進行降序排列。代碼1。

算法2：

每個元素逐個字符進行對比。代碼2。

代碼1

# Python2

class Solution:
    def largestNumber(self, nums):
        scmp = lambda a,b: int(b+a)-int(a+b)
        res = "".join(sorted(map(str, nums), cmp=scmp)).lstrip("0")
        return res or "0"

# Python3 

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums):
        key = cmp_to_key(lambda a,b: int(b+a)-int(a+b))
        res = "".join(sorted(map(str, nums), key=key)).lstrip("0")
        return res or "0"

代碼2

# Python2 

class Solution:
    def largestNumber(self,nums):
        def cxx(x,y):
            i = 0 
            sx= str(x)
            sy= str(y)
            while i< len(str(min(x,y))):
                if sx[i] > sy[i]:
                    return 1
                elif sx[i] < sy[i]:
                    return -1
                elif x == y:
                    return 0
                i+=1
            if i == len(sx):
                return -1 if sy[i]>sy[0] else 1
            if i == len(sy):
                return 1 if sx[i]>sx[0] else -1
        nx = sorted(nums,cmp=lambda x,y:cxx(x,y),reverse=True)        
        res = "".join(map(str, nx)).lstrip("0")
        return res or "0"

測試

t = Solution()
print(t.largestNumber([1, 20, 23, 4, 8]))
// 8423201

以上代碼已放到Hooyes的Github上開源，歡迎Fork或提建議。

largest-number.py

運行 python largest-number.py 即可以測試。

云服務器 GPU云服務器他們之間 js隨機一個整數 java中的整數除 c語言整數的存儲形式

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/41520.html

LeetCode 179. 最大數【c++/java詳細題解】

摘要：示例輸入輸出示例輸入輸出示例輸入輸出示例輸入輸出思路貪心給定一組非負數，重新排列使其組成一個最大的整數。具體過程如下自定義排序規則函數，將數組按照自定義排序規則重新排序。時間復雜度分析排序的時間復雜度為。 ...

tuantuan 2021-09-02 15:15 評論0 收藏0
小李飛刀：刷題第十三彈！

摘要：寫在前面今天的小李的目標是排序算法，果然還是要下手寫才會更有體會，也更記得住。排序算法冒泡排序主要是比對相鄰兩個數之間的大小關系，不斷將較大值交換至最后。寫在前面今天的小李的目標是排序算法，果然還是要下手寫才會更有體會，也更記得住。認真做題的分割線第一題 215. 數組中的第K個最大元素難度：中等在未排序的數組中找到第k個最大的元素。請注意，你需要找的是數組排序后的第k個最大的...

lixiang 2019-07-31 10:20 評論0 收藏0
犀牛書——CHAP7：數組

摘要：數組有以下特點無類型數組元素可以是任意元素。因此，當小于數組最大索引時，大于的數組元素會被刪除。原數組不會改變將數組元素轉換為字符串并連接在一起。默認將數組元素用，連接，傳入的參數即為連接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

Alfred 2019-08-19 18:40 評論0 收藏0
小李飛刀：做題第十一彈！

摘要：第五題對稱二叉樹難度簡單給定一個二叉樹，檢查它是否是鏡像對稱的。第十六題最大連續的個數難度簡單給定一個二進制數組，計算其中最大連續的個數。第十八題平方數之和難度簡單給定一個非負整數，你要判斷是否存在兩個整數和，使得。寫在前面最近忙著調教新裝備，沒有及時的寫題解，但是沒有在偷懶沒刷題喔~來認真整理下最近做的題目~ 之前考慮按tag來刷題，后來收到了推薦的leetcode題解，就根據上...

ytwman 2019-07-31 10:18 評論0 收藏0
LeetCode 213. 打家劫舍 II【c++/java詳細題解】

摘要：給定一個代表每個房屋存放金額的非負整數數組，計算你在不觸動警報裝置的情況下，今晚能夠偷竊到的最高金額。狀態表示表示偷竊號到號房間所能獲得的最高金額。下標均從開始打家劫舍我們已經知道了房間單排排列的狀態轉移方程，接下來思考房間環狀排列的做法。 ...

Kyxy 2021-09-23 11:21 評論0 收藏0