目录

1.题库描述

2.题目描述

3.核心思想

4.代码实现

1. 题库描述

众所周知啊，我们在计算机行业一路升级打怪的时候，不管是后端、算法甚至前端的同学，在面试或者开发过程中都或多或少会遇到这类算法题目。

那今天呢，我们就从 codetop 开始学习，看一下各大互联网公司（包含了字节、微软、美团、阿里、快手、腾讯、华为、百度等）的高频面试题目。

2. 题目描述

先从 top 100 开始，179. 最大数

我们先看一下题目描述，有一组非负整数 nums，需要我们重新排列一下顺序，让它组成一个最大的整数。

比如：

1）输入一个 [10, 2] 的数组，我们输出的最大整数就是 "210"；

2）输入 [3, 30, 34, 5, 9] 这一串数，我们输出的最大整数是以 9 开头的最大整数 "9534330"。

到这里啊，我们发现，其实这道题就是让我们给输入的数组排个序，然后根据排序的结果输出一个最大的整数（因为数组可能会比较长，所以我们输出的整数得是一个字符串）。

3. 核心思想

那本题作为一道中等难度的题目，肯定不可能是一般的排序那么简单，所以我们得观察一下，如何对数组里面的数字进行排序。

从题目示例 2 来看：

[3, 30, 34, 5, 9]

我们可以发现，要想获取一个最大的整数，最高位肯定是最大的数。所以排序原则是 最高位大的数尽量靠前。

根据这个原则，我们可以推断，如果要对 nums 里的两个数 nums[i]，nums[j] 进行排序（0<=i<j<=n-1，n为nums的长度）。那么我们可以假设，i 或者 j 在前面，将其进行组合，看看最终得出的整数哪个更大。比如，

i=0，j=1 时，3 和 30 进行组合，可以得出：330 和 303，不难发现，330比303更大，所以 3 排在 30之前，不用改动；

i=1，j=2时，30 和 34 进行组合：3034 和 3430，由于 3430 > 3034，所以我们需要让 34 排在 30 之前。

4. 代码实现

有了这个原则，我们就可以用 快速排序 对此题进行处理了（不熟悉快速排序的同学，可以看一下之前的文章：高效排序算法之快排），代码如下：

func largestNumber(nums []int) string {
    // 特殊情况处理，如果数组长度为0，直接输出
 if len(nums) == 0 {
  return ""
 }
 numStr := numsToString(nums)
 quickSort(numStr, 0, len(numStr)-1)
    
    // 如果不确定排序是否成功，可以打印一下排序之后的数组
 fmt.Println(numStr)
 var res string
 for _, str := range numStr {
  if res == "0" && str == "0" {
   continue
  }
  res += str
 }
 return res
}

// 快排开始
func quickSort(strs []string, left, right int) {
    // 判断特殊情况，当只有一个值时，直接返回
 if left >= right {
  return
 }
 p := partition(strs, left, right)
    // 继续对分界值两边的数做递归操作
 quickSort(strs, left, p-1)
 quickSort(strs, p+1, right)
}

// 经过一轮排序，获取一个分界值，分界值的左边都小于它，右边都大于或等于它
func partition(strs []string, left, right int) int {
    // 选取随机数
 i, k := left-1, left+rand.Intn(right-left+1)
 strs[right], strs[k] = strs[k], strs[right]
 for j := left; j < right; j++ {
  if strs[j]+strs[right] > strs[right]+strs[j] {
   i++
   strs[i], strs[j] = strs[j], strs[i]
  }
 }
 strs[i+1], strs[right] = strs[right], strs[i+1]
 return i + 1
}

// 把数字数组全部替换为字符串，因为需要我们用字符串输出，方便后续排序后直接拼接
func numsToString(nums []int) []string {
 var res []string
 for i := 0; i < len(nums); i++ {
  res = append(res, strconv.Itoa(nums[i]))
 }
 return res
}

提交结果：