179. Largest Number #

Problem #

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.

Problem Summary #

Given an array, arrange the elements in the array so that the final arranged number is the largest.

Solution Approach #

For this problem, it is easy to think of converting all the numbers into strings and using string comparison to sort them, so that those starting with 9 will definitely be at the front. However, there is one place where this approach is wrong. For example, when comparing “3” and “30”, “30” is greater than “3” in lexicographical order, so sorting this way would be incorrect. In fact, for this problem, “3” should be placed before “30”.

When comparing the size of 2 strings, we should not simply use lexicographical order; we also add an order.

aStr := a + b
bStr := b + a

By comparing the sizes of aStr and bStr, we can determine whether a is greater or b is greater.

For example, still using the example of “3” and “30”, compare the sizes of these 2 strings.

aStr := "3" + "30" = "330"
bStr := "30" + "3" = "303"

After padding the digits by concatenating them with each other before comparing, there is no problem. Obviously, here “3” is greater than “30”.

Code #

package leetcode

import (
	"strconv"
)

func largestNumber(nums []int) string {
	if len(nums) == 0 {
		return ""
	}
	numStrs := toStringArray(nums)
	quickSortString(numStrs, 0, len(numStrs)-1)
	res := ""
	for _, str := range numStrs {
		if res == "0" && str == "0" {
			continue
		}
		res = res + str
	}
	return res
}

func toStringArray(nums []int) []string {
	strs := make([]string, 0)
	for _, num := range nums {
		strs = append(strs, strconv.Itoa(num))
	}
	return strs
}
func partitionString(a []string, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		ajStr := a[j] + pivot
		pivotStr := pivot + a[j]
		if ajStr > pivotStr { // The condition here is the key
			i++
			a[j], a[i] = a[i], a[j]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}
func quickSortString(a []string, lo, hi int) {
	if lo >= hi {
		return
	}
	p := partitionString(a, lo, hi)
	quickSortString(a, lo, p-1)
	quickSortString(a, p+1, hi)
}