aboutsummaryrefslogtreecommitdiff
path: root/largest_number.py
blob: 8efe135c39315efd46c02c8fea9ce8677cf68f34 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 179. Largest Number

"""
given a list of non-negative integers 'nums', arrange them such that they
form the larget number and return it. since the result may be very large, so
you need to return a string instead of an integer.
"""


class Solution(object):
    def largestNumber(self, nums):
        self.quickSort(nums, 0, len(nums) - 1)
        return str(int("".join(map(str, nums))))

    def quickSort(self, nums, l, r):
        if l >= r:
            return
        pos = self.partition(nums, l, r)
        self.quickSort(nums, l, pos - 1)
        self.quickSort(nums, pos + 1, r)

    def partition(self, nums, l, r):
        low = l
        while l < r:
            if self.compare(nums[l], nums[r]):
                nums[l], nums[low] = nums[low], nums[l]
                low += 1
            l += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low


if __name__ == "__main__":
    obj = Solution()
    print(obj.largestNumber([10, 2]))  # expect: 210
    print(obj.largestNumber([3, 30, 34, 5, 9]))  # expect: 9534330