力扣：45 把数组排成最小的数

发表于

「这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战」

描述

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

  • 示例 1:
1
2
makefile复制代码输入: [10,2]
输出: "102"
  • 示例 2:
1
2
makefile复制代码输入: [3,30,34,5,9]
输出: "3033459"
  • 提示
1
matlab复制代码0 < nums.length <= 100

解析

根据题意，这一题最关键的部分就是自定义排序，一旦找到排序的奇点，就可以轻而易举解决这一题。 我们判断两个数字谁大谁小的依据是，str1+str2是否大于str2+str1，其实就是这么简单。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
scss复制代码class Solution {
    public String minNumber(int[] nums) {
        //第一种方法，全排列，但是比较麻烦
        //第二种方法就是按照一定顺序排列，也就是要重写比较器
        //从首位到末尾开始比较
        //所以手写一个冒泡，排好序以后用
        //用新的比较器写一个冒泡排序
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            strs[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strs, (o1, o2) -> (o1+o2).compareTo(o2+o1));
        StringBuilder sb = new StringBuilder();
        for (String x:strs) {
            sb.append(x);
        }
        return sb.toString();
    }
}

运行结果：

执行结果：通过

执行用时：4 ms, 在所有 Java 提交中击败了97.52%的用户

内存消耗：38 MB, 在所有 Java 提交中击败了45.05%的用户

  • 其他解法

下面这种方式是通过随机快排，切记排序不是简单对a,b排序，如排序12，543，那么应该比较的是12543 和 54312 这个直接找到每个数是多少位，然后相加即可 12000 + 54 与 54300 + 12 比较

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
css复制代码class Solution {
    public String minNumber(int[] nums) {
        return minNumber4(nums);
    }
    public String minNumber4(int[] nums){
       quickSortRandom(nums,0,nums.length-1);
       StringBuilder sb = new StringBuilder(nums.length);
       for(int i : nums) sb.append(i);
       return sb.toString();
    }
    public void quickSortRandom(int[] A,int low,int high){
        if(low < 0 || high >= A.length || low >= high ) return;
        int q = partition(A,low,high);
        quickSortRandom(A,low,q-1);
        quickSortRandom(A,q+1,high);
    }
    public int partition(int[] A,int low,int high){
        int rand = low + (int)(Math.random()*(high - low));
        swap(A,rand,high);
        int x = A[high],i = low - 1;
        long a,b;
        for(int j = low; j < high; j++){
            a = 10;b = 10;
            while(A[j] >= a) a *= 10;
            while(x >= b) b *= 10;
            if(A[j] * b + x <= A[j] + x * a){
                i++;
                swap(A,i,j);
            }
        }
        swap(A,i+1,high);
        return i + 1;
    }
    public void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%