每日一题《剑指offer》数组篇之把数组排成最小的数

终有救赎

发布于 2023-10-16 10:21:16

1680

发布于 2023-10-16 10:21:16

文章被收录于专栏：多线程

今日题目链接:把数组排成最小的数

把数组排成最小的数

难度:中等

描述

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

例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

1.输出结果可能非常大，所以你需要返回一个字符串而不是整数 2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

数据范围

0<=len(numbers)<=100

举例

解题思路

本题最直观的解法就是求出数组中所有数字的全排列，然后比较所有的排列，最后找到最小的排列，但是时间复杂度为O(n!)，所以不是一个好的解法。

换一种思路可以发现，本题实际上希望我们找到一个排序规则，数组根据这个排序规则进行重排之后可以连成一个最小的数字。要确定这样的排序规则，也就是对于两个数字m和n，通过一个规则确定哪个应排在前面。

根据题目要求，我们可以发现，两个数字m和n能拼接成mn和nm，如果mn<nm，那m应该在前；如果nm<mn，那么n应该在前。因此，我们得到的排序规则如下：

若mn>nm，则m大于n 若mn<nm，则m小于n 若mn=nm，则m等于n 根据上述规则，我们需要先把数字转换成字符串再进行比较，因为需要拼接起来。比较完之后按顺序连接成一个字符串即可。

编程实现(java)

import java.util.*;
public class Solution {
    public String PrintMinNumber(int [] numbers) {
        //空数组的情况
        if(numbers == null || numbers.length == 0)
            return "";
        String[] nums = new String[numbers.length];
        //将数字转成字符
        for(int i = 0; i < numbers.length; i++)
            nums[i] = numbers[i] + "";
        //按照重载排序
        Arrays.sort(nums, new Comparator<String>() {
            public int compare(String s1, String s2) {
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuilder res = new StringBuilder();
        //字符串叠加
        for(int i = 0; i < nums.length; i++)
            res.append(nums[i]);
        return res.toString();
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-10-12，如有侵权请联系 cloudcommunity@tencent.com 删除

编程