网站开发推荐书籍,合肥科技网站建设,公司招聘网站排行榜,河南最新新闻事件15条将数组排成最小的数 题目#xff1a;输入一个正整数的数组#xff0c;将数组中所有数字拼接在一起排列成一个新的数#xff0c;打印能拼接出来的所有数字中最小的一个#xff0c; 案例#xff1a;输入数组{12,4#xff0c;55}#xff0c;则能打印出最小的数组是#x…将数组排成最小的数 题目输入一个正整数的数组将数组中所有数字拼接在一起排列成一个新的数打印能拼接出来的所有数字中最小的一个 案例输入数组{12,455}则能打印出最小的数组是12455 首先还是最简单的做法我们求出数组中所有数字的全排列然后将每个排列的情况拼接成一个新的数字比较得到最小的数字情况。求数组的全排列问题我们在之前的文章数据结构与算法–字符串的排列组合问题 更具排列组合知识n个数组共有n个排列当数组元素比较多的时候时间复杂度会是一个非常大的数值运行会非常慢应该有更快的方案。 常规优化穷举法是为了避开了一个选择交换的过程如果只有两个元素我们找出小的放到前面那这个题目就转成了一个找数组的排序规则的过程。数组根据这个排序规则排列成一个最小的数字。要确定排序规则就需要比较两个数字也就是给出 mn两个数我们需要确定一个排序规则判断mn那个应该在前面这不是比较数字大小的问题。 根据题目要求两个数字mn能拼出mnnm两个数字。 如果mn nm那么我们应该输出mn也就是m应该在n前面我们定义m 小于 n如果mn nm那么我们应该输出nm也就是n在m前我们定义n 小于 m同样mn nm定义 m n以上中 是我们数学意义上的比较而大于小于等于是我们自己定义的大小关系。 那么我们接下来需要考虑的是怎么去拼接数字当给出数字mn我们直接计算的方式得到mnnm的关系并不难。但是还有一个关键问题当mn拼接后得到数字无法用int表达的时候超过int类型的范围那么我们就不能用普通的计算方式。有一个潜在的大数问题让我必须用字符串的方式来计算。 大数问题用字符串解决字符串的比较问题因为此处mn nm 两个数必然是两个长度相等的字符串那么比较他大小只需要按照字符串的大小比较规则就可以了。 基于以上分析我们可以先对数组中的所有数组进行快速排序 排序规则用我们自定义规则 从小到大排序后将所有数字依次拼接就得到了最小值。 经如上分析有如下代码
/*** 将数组中所有数据合并成一个数求出能排成的最小数** author liaojiamin* Date:Created in 12:00 2021/6/8*/
public class FinMinNumber {public static String pringMinNumber(int[] array) {if (array null || array.length 0) {return ;}if (array.length 1) {return String.valueOf(array[0]);}String[] str new String[array.length];for (int i 0; i array.length; i) {str[i] String.valueOf(array[i]);}quickSort(str, 0, str.length - 1);StringBuilder stringBuilder new StringBuilder();for (String s : str) {System.out.print(s , );stringBuilder.append(s);}System.out.println();return stringBuilder.toString();}/*** 快排法按从小到大排序字符串字符串大小规则自定义* */public static String[] quickSort(String[] str, Integer left, Integer right) {if (left right) {Integer temp quickSortSwap(str, left, right);quickSort(str, left, temp - 1);quickSort(str, temp 1, right);}return str;}public static Integer quickSortSwap(String str[], Integer left, Integer right) {if (left right) {String position str[left];while (left right){while (left right myCompareTO(str[right], position) 0) {right--;}if (left right) {str[left] str[right];left;}while (left right myCompareTO(str[left], position) 0) {left;}if (left right) {str[right] str[left];right--;}}str[left] position;}return left;}/*** 字符串大小规则比较* ab ba ab* ab ba ab* abba ab* */public static Integer myCompareTO(String a, String b){String ab ab;String ba ba;return ab.compareTo(ba);}public static void main(String[] args) {int[] str_1 {12, 34, 1, 34, 777, 33, 99, 86, 56, 9};System.out.println(pringMinNumber(str_1));}
}后续问题 如上实现方案中有两个问题 第一我定义了一种新的比较两个数的规则但是这种规则是我们想出来的并不是定理或者公第二我们定义的是比较两个数的规则但是用它来排序一个包含多个数字的数组最终得到的是否是我们需要的的最小数字 那么以上两点我们必须给出严格的数学证明来确保方案的准确 第一证明之前订阅的比较规则有效性。一个比较规则有效需满足三个条件自反性对称性传递性 自反性 显然如果ab ba 那么 a等于b对称性 如果a 小于 b则ab ba 所以ba ab,因此b 大于 a传递性 如果a 小于 b 则 ab ba。 假设a b都是十进制表示时候分别有1位m位有如下推断 如果有a 小于b ab a * 10 m b ba b* 101 a 若 ab ba 有 a * 10 m b b* 101 a a * 10 m - a b* 101 - b a(10m-1) b(101-1) a/(101-1) b/(10m-1) 同时如果有b 小于c则bc cb同样假设c十进制n位与以上证明一致得到 b/(10m -1) c(10n -1) 综上 a/(101-1) b/(10m-1) c(10n -1) a/(101-1) c(10n -1) a(10n -1) c(101-1) a * 10n c c * 101a ac ca ac 如上证明了这种比较规则满足自反性对称性传递性是一种有效的比较规则 以下还需要证明根据如上规则将数组排序后将数组中所有数字拼接起来得到的确实是最小值。 略太难了
上一篇数据结构与算法-- 数组中出现次数超过一半的数字时间复杂度的讨论 下一篇数据结构与算法–丑数
