- 01.题目要求
- 02.问题分析
- 03.实例代码
- 博客笔记大汇总【15年10月到至今】,包括Java基础及深入知识点,Android技术博客,Python学习笔记等等,还包括平时开发中遇到的bug汇总,当然也在工作之余收集了大量的面试题,长期更新维护并且修正,持续完善……开源的文件是markdown格式的!同时也开源了生活博客,从12年起,积累共计N篇[近100万字,陆续搬到网上],转载请注明出处,谢谢!所有博客陆续更新到GitHub上!
- 链接地址:https://github.com/yangchong211/YCBlogs
- 如果觉得好,可以star一下,谢谢!当然也欢迎提出建议,万事起于忽微,量变引起质变!
- 问题如下所示:
- 输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
- 示例 :
例如输入数组{3, 32, 321},则扫描输出这3 个数字能排成的最小数字321323。
- 第一种:直观解法
- 先求出这个数组中所有数字的全排列,然后把每个排列拼起来,最后求出拼起来的数字的最小值。
- 第二种:排序解法
- 找到一个排序规则,数组根据这个规则排序之后能排成一个最小的数字。要确定排序规则,就要比较两个数字,也就是给出两个数字m 和n,我们需要确定一个规则判断m 和n 哪个应该排在前面,而不是仅仅比较这两个数字的值哪个更大。
- 根据题目的要求,两个数字m 和n能拼接成数字m和m。如果mn < nm,那么我们应该打印出m,也就是m 应该排在n 的前面,我们定义此时m 小于n:反之,如果nm < mn,我们定义n小于m。如果mn=nm,m 等于n。在下文中,符号“<”、“>”及“=”表示常规意义的数值的大小关系,而文字“大于”、“小于”、“等于”表示我们新定义的大小关系。
- 接下来考虑怎么去拼接数字,即给出数字m和n,怎么得到数字m和m 并比较它们的大小。直接用数值去计算不难办到,但需要考虑到一个潜在的问题就是m 和n 都在int 能表达的范围内,但把它们拼起来的数字mn 和nm 用int 表示就有可能溢出了,所以这还是一个隐形的大数问题。
- 一个非常直观的解决大数问题的方法就是把数字转换成字符串。另外,由于把数字m 和n 拼接起来得到mn 和nm,它们的位数肯定是相同的,因此比较它们的大小只需要按照字符串大小的比较规则就可以了。
- 如下所示
public class Test { /** * 题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数, * 打印能拼接出的所有数字中最小的一个。 * @param array 输入的数组 * @return 输出结果 */ public static String printMinNumber(String[] array) { if (array == null || array.length < 1) { throw new IllegalArgumentException("Array must contain value"); } MComparator comparator = new MComparator(); quickSort(array, 0, array.length - 1, comparator); StringBuilder builder = new StringBuilder(256); for (String s : array) { builder.append(s); } return builder.toString(); } /** * 自定义的排序比较器,实现算法说明的排序原理 */ private static class MComparator implements Comparator<String> { @Override public int compare(String o1, String o2) { if (o1 == null || o2 == null) { throw new IllegalArgumentException("Arg should not be null"); } String s1 = o1 + o2; String s2 = o2 + o1; return s1.compareTo(s2); } } /** * 快速排序算法 * @param array 待排序数组 * @param start 要排序的起始位置 * @param end 要排序的结束位置 * @param comparator 自定义的比较器 */ private static void quickSort(String[] array, int start, int end, Comparator<String> comparator) { if (start < end) { String pivot = array[start]; int left = start; int right = end; while (start < end) { while (start < end && comparator.compare(array[end], pivot) >= 0) { end--; } array[start] = array[end]; while (start < end && comparator.compare(array[start], pivot) <= 0) { start++; } array[end] = array[start]; } array[start] = pivot; quickSort(array, left, start - 1, comparator); quickSort(array, start + 1, end, comparator); } } }
- 代码如下所示
public static void test() { String[] str = {"3","31","345"}; String num = printMinNumber(str); System.out.print(num); }
- 打印结果
- 313345
- 我的个人站点:
- github:https://github.com/yangchong211
- 知乎:https://www.zhihu.com/people/yczbj/activities
- 简书:http://www.jianshu.com/u/b7b2c6ed9284
- csdn:http://my.csdn.net/m0_37700275
- 喜马拉雅听书:http://www.ximalaya.com/zhubo/71989305/
- 开源中国:https://my.oschina.net/zbj1618/blog
- 泡在网上的日子:http://www.jcodecraeer.com/member/content_list.php?channelid=1
- 邮箱:yangchong211@163.com
- 阿里云博客:https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
- segmentfault头条:https://segmentfault.com/u/xiangjianyu/articles
- 掘金:https://juejin.im/user/5939433efe88c2006afa0c6e