目錄

1.題庫描述

2.題目描述

3.核心思想

4.代碼實現(xiàn)

1. 題庫描述

眾所周知啊，我們在計算機行業(yè)一路升級打怪的時候，不管是后端、算法甚至前端的同學，在面試或者開發(fā)過程中都或多或少會遇到這類算法題目。

那今天呢，我們就從 codetop?開始學習，看一下各大互聯(lián)網公司（包含了字節(jié)、微軟、美團、阿里、快手、騰訊、華為、百度等）的高頻面試題目。

2. 題目描述

先從 top 100 開始，179. 最大數(shù)

我們先看一下題目描述，有一組非負整數(shù) nums，需要我們重新排列一下順序，讓它組成一個最大的整數(shù)。

比如：

1）輸入一個 [10, 2] 的數(shù)組，我們輸出的最大整數(shù)就是 "210"；

2）輸入 [3, 30, 34, 5, 9] 這一串數(shù)，我們輸出的最大整數(shù)是以 9 開頭的最大整數(shù) "9534330"。

到這里啊，我們發(fā)現(xiàn)，其實這道題就是讓我們給輸入的數(shù)組排個序，然后根據(jù)排序的結果輸出一個最大的整數(shù)（因為數(shù)組可能會比較長，所以我們輸出的整數(shù)得是一個字符串）。

3. 核心思想

那本題作為一道中等難度的題目，肯定不可能是一般的排序那么簡單，所以我們得觀察一下，如何對數(shù)組里面的數(shù)字進行排序。

從題目示例 2 來看：

[3, 30, 34, 5, 9]

我們可以發(fā)現(xiàn)，要想獲取一個最大的整數(shù)，最高位肯定是最大的數(shù)。所以排序原則是 最高位大的數(shù)盡量靠前。

根據(jù)這個原則，我們可以推斷，如果要對 nums 里的兩個數(shù) nums[i]，nums[j] 進行排序（0<=i<j<=n-1，n為nums的長度）。那么我們可以假設，i 或者 j 在前面，將其進行組合，看看最終得出的整數(shù)哪個更大。比如，

i=0，j=1 時，3 和 30 進行組合，可以得出：330 和 303，不難發(fā)現(xiàn)，330比303更大，所以 3 排在 30之前，不用改動；

i=1，j=2時，30 和 34 進行組合：3034 和 3430，由于 3430 > 3034，所以我們需要讓 34 排在 30 之前。

4. 代碼實現(xiàn)

有了這個原則，我們就可以用 快速排序 對此題進行處理了（不熟悉快速排序的同學，可以看一下之前的文章：高效排序算法之快排），代碼如下：

func largestNumber(nums []int) string {
 ? ?// 特殊情況處理，如果數(shù)組長度為0，直接輸出
 if len(nums) == 0 {
 ?return ""
 }
 numStr := numsToString(nums)
 quickSort(numStr, 0, len(numStr)-1)
 ? ?
 ? ?// 如果不確定排序是否成功，可以打印一下排序之后的數(shù)組
 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)
 ? ?// 繼續(xù)對分界值兩邊的數(shù)做遞歸操作
 quickSort(strs, left, p-1)
 quickSort(strs, p+1, right)
}

// 經過一輪排序，獲取一個分界值，分界值的左邊都小于它，右邊都大于或等于它
func partition(strs []string, left, right int) int {
 ? ?// 選取隨機數(shù)
 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
}

// 把數(shù)字數(shù)組全部替換為字符串，因為需要我們用字符串輸出，方便后續(xù)排序后直接拼接
func numsToString(nums []int) []string {
 var res []string
 for i := 0; i < len(nums); i++ {
 ?res = append(res, strconv.Itoa(nums[i]))
 }
 return res
}

提交結果：