leetcode算法题--把数组排成最小的数

原题链接：https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/?envType=study-plan-v2&envId=coding-interviews

一开始没想到排序可以这么写，写复杂了。。

func minNumber(nums []int) string {
    n := len(nums)
    sort.Slice(nums, func(i, j int) bool {
        s1 := strconv.Itoa(nums[i])
        s2 := strconv.Itoa(nums[j])
        if s1 + s2 < s2 + s1 {
            return true
        }
        return false
    })
    var res string
    for i := 0; i < n; i ++ {
        res += strconv.Itoa(nums[i])
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

快速排序写法

func minNumber(nums []int) string {
    n := len(nums)
    sl := make([]string, 0)
    for _, num := range nums {
        sl = append(sl, strconv.Itoa(num))
    }
    var quickSort func(l, r int)
    quickSort = func(l, r int) {
        if l >= r {
            return
        }
        pivot := sl[l] 
        i, j := l, r
        for i < j {
            for j > i && sl[j] + pivot >= pivot + sl[j] {
                j--
            }
            sl[i] = sl[j]
            for j > i && sl[i] + pivot <= pivot + sl[i] {
                i++
            }
            sl[j] = sl[i]
        }
        sl[i] = pivot 
        quickSort(l, i-1)
        quickSort(i+1, r)
    }
    quickSort(0, n-1)
    var res string
    for _, s := range sl {
        res += s
    }
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34