179.md

Largest Number

题目:

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: "210"
Example 2:

Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

思路：

解法1：排序。

比较规则：9,43,431,4344441,4344445

按高位比较，如果同一高位较大者，则排在前面。 如9最大排在最前面。

当相同时，继续向后比较，知道段的字符串到结尾。到结尾的时候。看较长字符串. 如431 和 43。前高两位43相同，则看较长s=431,那1和第一个字符比较，1较小，将43排在431前面。

而当4344445和43比较的时候中间的4一直和首字符4相等，继续向后寻找，知道5>4。所以4344445排在43前面。

按上述规则结果为[9,4344445,43,4344441,431]

代码：

解法1

class Solution(object):
    _nums = []
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if nums==[]:
            return "0"
        for num in nums:
            self._nums.append(str(num))
        self.quick_sort(0, len(self._nums)-1)
        result = ""
        for s in self._nums:
            result += s
        return result
        
    def greater_equal(self, s1, s2):
        #s1>=s2 return True
        l = min(len(s1),len(s2))
        for i in range(l):
            if s1[i]>s2[i]:
                return True
            elif s1[i]<s2[i]:
                return False
            else:
                continue
        if len(s1)==len(s2):
            return True
        if len(s1)>len(s2):
            while l<len(s1):
                if s1[l]>s1[0]:
                    return True
                elif s1[l]<s1[0]:
                    return False
                else:
                    l += 1
        else:
            while l<len(s2):
                if s2[l]>s2[0]:
                    return False
                elif s2[l]<s2[0]:
                    return True
                else:
                    l += 1
        return True
        
    def partition(self, first, last):
        key = self._nums[first]
        first_greater = first
        for cur in range(first, last+1):
            if self.greater_equal(self._nums[cur], key):
                self._nums[cur], self._nums[first_greater] = self._nums[first_greater], self._nums[cur]
                first_greater += 1
        self._nums[first], self._nums[first_greater-1] = self._nums[first_greater-1], self._nums[first]
        return first_greater-1
    
    def quick_sort(self, first, last):
        if first <= last:
            mid = self.partition(first, last)
            self.quick_sort(first, mid-1)
            self.quick_sort(mid+1, last)