剑指 Offer 45. 把数组排成最小的数

题目描述

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

输入输出

1
2
3
4
5
输入: [10,2]
输出: "102"

输入: [3,30,34,5,9]
输出: "3033459"

基本思路

  • [3, 30]举例：330>303 则3在30后边
  • 以下”+”是前后拼接起来的意思
  • x+y > y+x x”大于”y x在y后边
  • x+y < y+x x”小于”y x在y前边
  • Java中 x.compareTo(3)
    • x>3 返回1
    • x=3 返回0
    • x<3 返回-1

java实现

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 使用接口
class Solution {
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(str, (x,y) -> (x+y).compareTo(y+x));
        StringBuilder res = new StringBuilder();
        for(String s:str){
            res.append(s);
        }
        return res.toString();
    }
}

// 手写快排
class Solution {
    public String minNumber(int[] nums) {
        String[] str = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            str[i] = String.valueOf(nums[i]);
        }
        quick_sort(str, 0, str.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s:str){
            res.append(s);
        }
        return res.toString();
    }

    public void quick_sort(String[] strs, int low, int high){
        if(low < high){
            int middle = getMiddle(strs, low, high);
            quick_sort(strs, low, middle - 1);
            quick_sort(strs, middle + 1, high);
        }
    }

    public int getMiddle(String[] strs, int low, int high){
        String pivot = strs[low];
        while(low < high){
            while(low < high && ((strs[high] + pivot).compareTo(pivot + strs[high]) ) >= 0 ){
                high--;
            }
            strs[low] = strs[high];
            while(low < high && ((strs[low] + pivot).compareTo(pivot + strs[high])) <= 0 ){
                low++;
            }
            strs[high] = strs[low];
        }
        strs[low] = pivot;
        return low;
    }
}