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.

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Sorting

Data structures

Greedy algorithms

Starter code: class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        

Solutions:
class Solution:

	def largestNumber(self, nums):
		nums = [str(n) for n in nums]
		nums.sort(reverse=True)
		for i in range(1, len(nums)):
			if len(nums[i - 1]) > len(nums[i]):
				ran = len(nums[i])
				j = i
				while j - 1 >= 0 and nums[j - 1][:ran] == nums[j] and (nums[j - 1] + nums[j] <= nums[j] + nums[j - 1]):
					(nums[j - 1], nums[j]) = (nums[j], nums[j - 1])
					j -= 1
		return str(int(''.join(nums)))


class Solution:

	class MyNumber:

		def __init__(self, v):
			self.str_val = str(v)
			self.val = [int(x) for x in self.str_val]
			self.n = len(self.val)

		def __cmp__(self, other):
			n1 = self.str_val + other.str_val
			n2 = other.str_val + self.str_val
			return 0 if n1 == n2 else 1 if n1 > n2 else -1

	def largestNumber(self, nums):
		if all((x == 0 for x in nums)):
			return '0'
		myns = [self.MyNumber(x) for x in nums]
		for i in range(len(nums)):
			for j in range(i + 1, len(nums)):
				if myns[j].__cmp__(myns[i]) > 0:
					t = myns[i]
					myns[i] = myns[j]
					myns[j] = t
		return ''.join([x.str_val for x in myns])


class Solution:

	def largestNumber(self, nums):
		maxPos = 0
		maxNum = ''
		res = ''
		while nums:
			for i in range(len(nums)):
				cur = nums[i]
				if str(cur) + maxNum >= maxNum + str(cur):
					maxNum = str(cur)
					maxPos = i
			nums.pop(maxPos)
			res += maxNum
			maxPos = 0
			maxNum = ''
		if res[0] == '0':
			return '0'
		return res


class Solution:

	def largestNumber(self, nums):
		strs = [str(num) for num in nums]

		def bigger(str1, str2):
			if int(str1 + str2) >= int(str2 + str1):
				return str1
			else:
				return str2
		answer = ''
		current = strs
		while current:
			maximum = current[0]
			for i in range(len(current)):
				maximum = bigger(maximum, current[i])
			answer += maximum
			current.remove(maximum)
		if answer[0] == '0':
			return '0'
		return answer


class Solution:

	def largestNumber(self, nums):
		if nums is None or len(nums) == 0:
			return ''
		for i in range(len(nums) - 1, -1, -1):
			for j in range(len(nums) - 1, len(nums) - i - 1, -1):
				e1 = str(nums[j - 1])
				e2 = str(nums[j])
				if e1 + e2 < e2 + e1:
					t = nums[j]
					nums[j] = nums[j - 1]
					nums[j - 1] = t
		ans = ''
		for n in nums:
			if n == 0 and ans == '':
				continue
			ans += str(n)
		return '0' if len(ans) == 0 else ans


class Solution:

	def largestNumber(self, nums):
		import functools
		nums_str = []
		for each in nums:
			nums_str.append(str(each))
		result = ''.join(sorted(nums_str, key=functools.cmp_to_key(self.comparator)))
		if int(result) == 0:
			return '0'
		else:
			return result

	def comparator(self, a, b):
		num1 = a + b
		num2 = b + a
		if num1 > num2:
			return -1
		elif num2 > num1:
			return 1
		else:
			return 0


class Solution:

	def sorting(self, numstr):
		newnumstr = []
		for i in range(0, len(numstr)):
			for j in range(1, len(numstr) - i):
				if numstr[j - 1] + numstr[j] < numstr[j] + numstr[j - 1]:
					temp = numstr[j - 1]
					numstr[j - 1] = numstr[j]
					numstr[j] = temp

	def largestNumber(self, nums):
		matrix = dict()
		for num in nums:
			numstr = str(num)
			if numstr[0] not in matrix:
				matrix[numstr[0]] = []
			matrix[numstr[0]].append(numstr)
		print(matrix)
		ret = ''
		for i in range(9, -1, -1):
			if str(i) in matrix:
				prenums = matrix[str(i)]
				self.sorting(prenums)
				ret += ''.join(prenums)
		return str(int(ret))


class Solution:

	def largestNumber(self, nums):

		def lexic_comp(a, b):
			ab = str(a) + str(b)
			ba = str(b) + str(a)
			if ab > ba:
				return -1
			elif ba > ab:
				return 1
			return 0
		import functools
		nums.sort(key=functools.cmp_to_key(lexic_comp))
		return str(int(''.join(map(str, nums))))


class Solution:

	def largestNumber(self, nums):
		s = self.sort(nums)
		if s.startswith('0'):
			return '0'
		else:
			return s

	def sort(self, nums):
		if not nums:
			return ''
		else:
			pivot = nums[0]
			left = []
			right = []
			for i in range(1, len(nums)):
				if self.compare(nums[i], pivot):
					left.append(nums[i])
				else:
					right.append(nums[i])
			return self.sort(left) + str(pivot) + self.sort(right)

	def compare(self, num1, num2):
		(num1, num2) = (str(num1), str(num2))
		return int(num1 + num2) > int(num2 + num1)


class Solution:

	def largestNumber(self, nums):

		def cmp_to_key(mycmp):

			class K:

				def __init__(self, obj, *args):
					self.obj = obj

				def __lt__(self, other):
					return mycmp(self.obj, other.obj) < 0

				def __gt__(self, other):
					return mycmp(self.obj, other.obj) > 0

				def __eq__(self, other):
					return mycmp(self.obj, other.obj) == 0

				def __le__(self, other):
					return mycmp(self.obj, other.obj) <= 0

				def __ge__(self, other):
					return mycmp(self.obj, other.obj) >= 0

				def __ne__(self, other):
					return mycmp(self.obj, other.obj) != 0
			return K

		def compare(n1, n2):
			l1 = len(n1)
			l2 = len(n2)
			i = 0
			if l1 != l2:
				tmp = n1
				n1 = n1 + n2
				n2 = n2 + tmp
				l1 = l1 + l2
			while i < max(l1, l2):
				if n1[i] < n2[i]:
					return -1
				elif n1[i] > n2[i]:
					return 1
				i += 1
			return 0

		def convert(num):
			if num == 0:
				return [0]
			res = []
			while num:
				res.append(num % 10)
				num //= 10
			res.reverse()
			return res
		nums = list(map(convert, nums))
		nums.sort(key=cmp_to_key(compare), reverse=True)
		print(nums)
		res = [str(c) for num in nums for c in num]
		res = ''.join(res).lstrip('0')
		if not res:
			res = '0'
		return res