方法一:
暴力枚举:时间复杂度为O(n!)
import java.util.ArrayList; public class Solution { String[] strArr; int[] vis; Long res = Long.MAX_VALUE; public String PrintMinNumber(int [] numbers) { // 暴力枚举 if(numbers == null || numbers.length==0) return ""; strArr = new String[numbers.length]; vis = new int[numbers.length]; dfs(0,numbers); return String.valueOf(res); } void dfs(int x,int[] numbers){ if(x == numbers.length){ StringBuilder builder = new StringBuilder(); for(String str: strArr){ builder.append(str); } res = Math.min(res,Long.parseLong(builder.toString())); } for(int i=0;i<numbers.length;i++){ if(vis[i] == 0){ vis[i] = 1; strArr[x] = String.valueOf(numbers[i]); dfs(x+1,numbers); vis[i]=0; } } } }
自定义排序:题目要求我们给出一个“最小”的数,这种最值问题可以想到使用排序来解决。
这里使用了贪心的思想:排序得到的结果一定是全局最小的。
import java.util.ArrayList; public class Solution { public String PrintMinNumber(int [] numbers) { // 自定义排序 quickSort(numbers,0,numbers.length-1); StringBuffer buffer = new StringBuffer(); for(int i:numbers){ buffer.append(i); } return buffer.toString(); } void quickSort(int[] a, int left, int right){ if(left >= right){ return; } int i=left, j=left; while(j<right){ if(compare(a[j],a[right])){ int tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; j++; }else { j++; } } int tmp = a[i]; a[i] = a[right]; a[right] = tmp; quickSort(a,left,i-1); quickSort(a,i+1,right); } boolean compare(int a, int b){ Long ab = Long.parseLong(String.valueOf(a) + b); Long ba = Long.parseLong(String.valueOf(b) + a); return ab<ba; // 返回a是否“小于”b } }