0179. Largest Number

179. 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.

题目大意 #

给出一个数组,要求排列这些数组里的元素,使得最终排列出来的数字是最大的。

解题思路 #

这一题很容易想到把数字都转化为字符串,利用字符串比较,来排序,这样 9 开头的一定排在最前面。不过这样做有一个地方是错误的,比如:“3” 和 “30” 比较,“30” 比 “3” 的字符序要大,这样排序以后就出错了。实际上就这道题而言, “3” 应该排在 “30” 前面。

在比较 2 个字符串大小的时候,不单纯的只用字符串顺序进行比较,还加入一个顺序。

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

通过比较 aStr 和 bStr 的大小来得出是 a 大还是 b 大。

举个例子,还是 “3” 和 “30” 的例子,比较这 2 个字符串的大小。

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

通过互相补齐位数之后再进行比较,就没有问题了。很显然这里 “3” 比 “30” 要大。

代码 #


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 { // 这里的判断条件是关键
			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)
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者