剑指offer45-把数组排成最小的数

原题(来源Leetcode)

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

示例 1:

输入: [10,2] 输出: "102"

示例 2:

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

提示:

  • 0 < nums.length <= 100

说明:

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

解法

思想

将数组排序,类似于动态规划的思想,两个数之间相互连接比较一下。

代码

class Solution {
    public String minNumber(int[] nums) {
        String[] strings = new String[nums.length];
        for(int i = 0;i<nums.length;i++){
            strings[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(strings,(s1,s2)->{
            String link1 = s1+s2;
            String link2 = s2+s1;
            for(int i = 0;i<link1.length();i++){
                if(link1.charAt(i)!=link2.charAt(i)) return link1.charAt(i)-link2.charAt(i);
            }
            return 0;
        });

        StringBuilder sb = new StringBuilder();
        for(String i:strings){
            sb.append(i);
        }
        return sb.toString();
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer45-%e6%8a%8a%e6%95%b0%e7%bb%84%e6%8e%92%e6%88%90%e6%9c%80%e5%b0%8f%e7%9a%84%e6%95%b0/

发表评论

电子邮件地址不会被公开。