最大数

原创
2019/09/04 14:22
阅读数 210

一、题目

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

示例 1:

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


示例 2:

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


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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/largest-number

 

二、解答

1.解题思路

首先拿到这道题,我们想到的是怎么样才能得出最大数?在草稿本上画一画,会发现这是一道排序题?!需要先找到排序的规律,然后选择一种排序算法。

经过我的深思熟虑,发现这道题的排序思路类似于基数排序,但又不是完全定义的基数排序。

随后参考了一下别人的思路。发现这道题要自定义一个排序算法:

    给两个数->两个数拼接起来->判断哪种拼接方法得到最大的数,返回顺序。

 

2.算法

    定义一种上述说明的排序方法

    使用冒泡(也可以使用其它复杂度较低的算法,偷懒用冒泡)排序算法对数列进行排序

    将排完的数列拼接成字符串

    如果字符串前面有0则去掉,全是0则答案等于0

 

3.代码

class Solution:
    def getAddMax(self, num1, num2):

        '''
        两个数拼接,返回最大的
        :param str1: 数1
        :param str2: 数2
        :return: 最大的数
        '''
        rs1 = int(str(num1) + str(num2))
        rs2 = int(str(num2) + str(num1))
        if rs1 > rs2:
            return rs1
        else:
            return rs2


    def compareTo(self, oldNum, newNum):
        '''
            两个数拼接,返回较大的拼接方式
        :param oldNum: 第一个数
        :param newNum: 第二个数
        :return: 较大的数
        '''
        rs1 = int(str(oldNum) + str(newNum))
        rs2 = int(str(newNum) + str(oldNum))
        if rs1 > rs2:
            return [oldNum,newNum]
        else:
            return [newNum,oldNum]
    def largestNumber(self, l: List[int]) -> str:
        '''
            对数列进行排序,使得组合起来的数字最大
        :param l: 数列
        :return:
        '''
        ans = ''
        ans2 = ''
        #  使用冒泡排序吧
        for i in range(len(l)):
            j = i
            while j < len(l):
                # 排序
                if self.compareTo(l[i], l[j]) != [l[i], l[j]]:
                    # 比较出来相反则交换顺序
                    tmp = l[i]
                    l[i] = l[j]
                    l[j] = tmp
                j += 1

        for index,elem in enumerate(l):
            ans += str(elem)
        # 前面的0需要去掉
        first_pos = True    # 字符串前面有0
        ans2 = list(ans)
        for i in range(len(ans)):
            if first_pos and ans[i] == '0':
                #   第一个位置为0就不进栈
                ans2.pop(0)
            elif first_pos and ans[i] != '0':
                first_pos = False
                break
        if len(ans2) == 0:
            ans2.append('0')
        ans = ''
        for i, e in  enumerate(ans2):
            ans += e
        return ans
        

emmm,这个代码就把答案跑出来了,完全没有优化。

4.结果(三次均跑出228ms, 222个测试用例)

 

5.思考

这道题难度中等,关键思路在于自定义一种排序算法对数列进行排序。其中上述代码采用了冒泡排序,效率比较低,因此这是一个值得改进的地方,另外,代码有点乱,使用了比较多的for循环,同时使用了许多不相关的变量,因此,该算法还有很大的改进空间。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部