算法题：剑指 Offer 45. 把数组排成最小的数 时空10ms（题目+思路+代码+注释）

算法题：剑指 Offer 45. 把数组排成最小的数 时空10ms（题目+思路+代码+注释）

题目

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

示例 1:

输入: [10,2] 输出: “102” 示例 2:

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

提示:

0 < nums.length <= 100 说明:

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

思路

要组成最小的数，首先肯定把最小的放最前面去，照着这个思路我们可以先做一个简单实现，然后我们会发现好像长度不同也会有不同，因此我们对长度统一到最长的一个的长度。比如12 和123去比较，我们得把12放前面123放后面，那么我们对12补位成122，按最后一位往后补，最后会发现会有局部的数据欺骗到了我们算法排序，可以逐个对象左右比对一次即可。

代码

public class Solution {public String minNumber(int[] nums) { // 求最大数 int max = nums[0]; for (int i : nums) { if (i > max) { max = i; } } // 求每个数补位后需要满足的最小数 long min = 1; while (min <= max) { min *= 10; } min /= 10; // 填充到对象 List numObjList = new ArrayList<>(nums.length); for (int i = 0; i < nums.length; i++) { numObjList.add(new NumObj(nums[i], min)); } // 排序 numObjList.sort((v1, v2) -> (int) (v1.cmp - v2.cmp)); //解决欺骗数据 for (int i = 0; i < nums.length - 1; i++) { if ((numObjList.get(i).num + "" + numObjList.get(i + 1).num).compareTo(numObjList.get(i + 1).num + "" + numObjList.get(i).num) > 0) { //需要换位 NumObj t = numObjList.get(i); numObjList.set(i, numObjList.get(i + 1)); numObjList.set(i + 1, t); } } // 组装结果 StringBuilder ret = new StringBuilder(); numObjList.forEach(numObj -> ret.append(numObj.num)); return ret.toString(); }}class NumObj { /** * 原本的数字 */ public int num; /** * 补齐位数后的用来比对的数 */ public long cmp; public NumObj(int num, long min) { this.num = num; long cmp = num; long cmpLast = cmp % 10; if (num > 0) { while (cmp < min) { cmp = cmp * 10 + cmpLast; } } this.cmp = cmp;// System.out.println(String.format("num %s根据min %s 映射为%s", num, min, cmp)); }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。