题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。
最简单直白的做法是排列出所有可能的数字,然后选出其中最小的那一个数作为返回结果。涉及到穷举出所有可能的排列结果,当然就采用回溯法求解。
public String PrintMinNumber(int [] numbers) { if (numbers == null || numbers.length == 0) { return null; } if (numbers.length == 1) { return String.valueOf(numbers[0]); } //最小值存储变量 StringBuilder min = new StringBuilder("9999999999999999999999999999999"); //标记数组,标记数组中元素是否有被访问过 boolean[] visited = new boolean[numbers.length]; backing(numbers, new LinkedList<Integer>(), min, visited); return min.toString(); } /** * 回溯函数:穷举出数组元素所有可能组成的数字 * @param numbers * @param path 路径,存储选择的一个结果 * @param min * @param visited */ private void backing(int[] numbers, LinkedList<Integer> path, StringBuilder min, boolean[] visited) { //当路径变量长度等于数组长度,表示已经用数组所有元素排列出了一个可能结果。判断他与最小值之间的大熊啊关系进行处理 if (path.size() == numbers.length) { String tem = ""; for (int i = 0; i < path.size(); i++) { tem += path.get(i); } if (tem.compareTo(min.toString()) < 0) { min.delete(0, min.length()); min.append(tem); } } //回溯函数的关键部分:路径的选择。 //由于是全排列,每次都是从0开始,只要为访问过,就可以再次加入路径变量中 for (int i = 0; i < numbers.length; i++) { if (visited[i]) { continue; } visited[i] = true; path.add(numbers[i]); backing(numbers, path, min, visited); visited[i] = false; path.removeLast(); } }