剑指offer（寻找最小数）

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数， 打印能拼接出的所有数字中最小的一个。 则打印出这三个数字能排成的最小数字为321323。

思路

* 1、此采用递归实现数组的全排列，拼接每组全排列成为新的数字保存至数组 * 2、比较每组数字，输出最小值

实验代码

package com.offer; import java.util.ArrayList; import java.util.Arrays; public class PrintMinNumber_sul { static ArrayList<String> num_all = new ArrayList(); public String PrintMinNumber(int [] numbers) { permutation(numbers,0); String min = num_all.get(0); //---------------开始比较数字--------------------- for (int i = 1;i<num_all.size();i++){ String a = num_all.get(i); if(Integer.parseInt(a)<Integer.parseInt(min)) min = a; } return min; } //----------递归实现对原数组进行全排列，排列拼接的数字保存在numarray中------------------------- public static void permutation(int[] array,int start){ if(start==array.length){ StringBuffer temp = new StringBuffer(); for (int i = 0;i<array.length;i++){ temp.append(Integer.toString(array[i])); } String s = temp.toString(); num_all.add(s); } else for(int i=start;i<array.length;++i){ swap(array,start,i); // 交换元素 permutation(array,start+1); //交换后，再进行全排列算法 swap(array,start,i); //还原成原来的数组，便于下一次的全排列 } } public static void swap(int[] array,int a,int b){ int temp = array[a]; array[a] = array[b]; array[b] = temp; } public static void main(String ags[]){ int[] a = {3,32,321}; int[] b = {1,2,3,4,5}; PrintMinNumber_sul test = new PrintMinNumber_sul(); PrintMinNumber_sul test2 = new PrintMinNumber_sul(); System.out.println(test.PrintMinNumber(a)); System.out.println(test2.PrintMinNumber(b)); } }