179. 最大数 [medium]

https://leetcode-cn.com/problems/largest-number/

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210

示例 2:

输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

通过次数34,510 | 提交次数94,413

Second Try

2020-07-15

使用快排 + 简易的字符串比较compare函数。

在First Try中，对字符串的比较用了逐字符串的比较方法，还用上了递归，结果一看题解，其实只要从大处着手，直接对两字符串按两种拼接顺序后的字符进行比较的结果就行了。

对于快排，之前写了好几次，还写了链表的快排，以为已经很熟练了，结果还是一边写一遍调bug。对于许多边界条件，很容易考虑不到位。尤其对于pivot点的选取，还是选取0点比较方便；然后在排序完成之后，需要把pivot点放到中间位置，这个顺序才不会错乱。

anyway, 又一次对老算法进行了练手，快排虽然一边写一边调bug，但对基础原理熟悉后也算是随手写出来，也能随手调bug，不错。

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        # 搞个快排 + 简单版compare
        def compare(ni, nj):
            ni, nj = str(ni), str(nj)
            return int(ni + nj) > int(nj + ni)
        
        def qsort(nums,left, right, compare):
            if left >= right:
                return 
            # 还不如直接选择第0个作为pivot
            idx = left + 1
            for i in range(left + 1, right + 1):
                if compare(nums[i], nums[left]):
                    nums[idx], nums[i] = nums[i], nums[idx]
                    idx += 1
            nums[left], nums[idx - 1] = nums[idx - 1], nums[left] # 把pivot点放回中间，差点忘了
            qsort(nums, left, idx - 2, compare)
            qsort(nums, idx, right, compare)

        if not len(nums):
            return ""
            
        qsort(nums, 0, len(nums) - 1, compare = compare)
        rv = "".join([str(n) for n in nums])
        return str(int(rv)) 

执行用时：36 ms, 在所有 Python 提交中击败了37.93%的用户
内存消耗：12.8 MB, 在所有 Python 提交中击败了14.29%的用户

First Try

2020-07-16

本来直接用字符串进行排序，后来发现有一些情况比较难处理，比如(30, 3), (34, 342), (34, 3435), 这些都很难办。在字符串排序中，"3" < "30", 结果变成[30, 3], 但按题意排序应该是[3, 30],这就错误了。

所以考虑额外写个compare函数，其实这是java里面排序函数里有的概念，但是python只有key，因此只能自己重新写个简单的冒泡排序。

compare函数里面，需要特殊考虑的是递归问题，尤其对于(34, 34342)和(34, 34345)这两种情况其实是不同的排列，用递归才能解决。

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        def compare(ni, nj):
            ni, nj = str(ni), str(nj)
            for i in range(min(len(ni), len(nj))):
                if ni[i] > nj[i]:
                    return True 
                elif ni[i] < nj[i]:
                    return False 
            # 3430 vs 34, 3435 vs 3434, 343430 vs 34 , 343435 vs 34 
            # 以为有上面的情况，才需要写成递归模式
            if len(ni) < len(nj):
                return compare(ni, nj[len(ni):]) 
            elif len(ni) > len(nj):
                return compare(ni[len(nj):], nj)
            return True 

        # 冒泡排序，好久没写差点没写出来
        for i in range(0, len(nums) - 1):
            maxidx = i 
            for j in range(i + 1, len(nums)):
                if compare(nums[j], nums[maxidx]):
                    maxidx = j 
            nums[i], nums[maxidx] = nums[maxidx], nums[i]
        rv = ''.join([str(i) for i in nums])
        # "00"要求返回的是"0"而不是"00", 对于python直接就处理了
        return str(int(rv)) 

执行用时：100 ms, 在所有 Python 提交中击败了11.08%的用户
内存消耗：12.7 MB, 在所有 Python 提交中击败了14.29%的用户

failed try

使用字符串直接排序的错误解答，遇到[3, 30]就悲剧了。

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        # 挂掉的 [3,30,34,5,9]
        snums = sorted([str(i) for i in nums], reverse = True)
        rv = ''.join(snums)
        return rv 