📑 题目：179. 最大数

🚀 本题 LeetCode 传送门

题目大意

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

解题思路

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

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

  1. aStr := a + b
  2. bStr := b + a

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

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

  1. aStr := ""3"" + ""30"" = ""330""
  2. bStr := ""30"" + ""3"" = ""303""

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

代码

  1. package leetcode
  3. import (
  4.  ""strconv""
  5. )
  7. func largestNumber(nums []int) string {
  8.  if len(nums) == 0 {
  9.   return """"
  10.  }
  11.  numStrs := toStringArray(nums)
  12.  quickSortString(numStrs, 0, len(numStrs)-1)
  13.  res := """"
  14.  for _, str := range numStrs {
  15.   if res == ""0"" && str == ""0"" {
  16.    continue
  17.   }
  18.   res = res + str
  19.  }
  20.  return res
  21. }
  23. func toStringArray(nums []int) []string {
  24.  strs := make([]string, 0)
  25.  for _, num := range nums {
  26.   strs = append(strs, strconv.Itoa(num))
  27.  }
  28.  return strs
  29. }
  30. func partitionString(a []string, lo, hi int) int {
  31.  pivot := a[hi]
  32.  i := lo - 1
  33.  for j := lo; j < hi; j++ {
  34.   ajStr := a[j] + pivot
  35.   pivotStr := pivot + a[j]
  36.   if ajStr > pivotStr { // 这里的判断条件是关键
  37.    i++
  38.    a[j], a[i] = a[i], a[j]
  39.   }
  40.  }
  41.  a[i+1], a[hi] = a[hi], a[i+1]
  42.  return i + 1
  43. }
  44. func quickSortString(a []string, lo, hi int) {
  45.  if lo >= hi {
  46.   return
  47.  }
  48.  p := partitionString(a, lo, hi)
  49.  quickSortString(a, lo, p-1)
  50.  quickSortString(a, p+1, hi)
  51. }