输入一个非负整数数组numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组[3,32,321],则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大,所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
2.拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
数据范围:
0<=len(numbers)<=100
[11,3]
"113"
[]
""
[3,32,321]
"321323"
import java.util.*; import java.util.ArrayList; public class Solution { public static String min_val=""; public String PrintMinNumber(int [] numbers) { if(numbers==null||numbers.length==0) return ""; dfs(numbers,0); return String.valueOf(min_val); } public void dfs(int[] nums,int startindex){ StringBuilder builder=new StringBuilder(); for(int i=0;i<nums.length;i++) builder.append(nums[i]); String str=builder.toString(); min_val=minStr(min_val,str); for(int cursor=startindex;cursor<nums.length;cursor++){ swap(nums,startindex,cursor); dfs(nums,startindex+1); swap(nums,startindex,cursor); } } public void swap(int[] nums,int x,int y){ int temp=nums[x]; nums[x]=nums[y]; nums[y]=temp; } public String minStr(String str1,String str2){ if(str1==null||str1=="") return str2; if(str2==null||str2=="") return str1; if(str1.startsWith("0")&&str2.startsWith("0")==false) return str2; if(str2.startsWith("0")&&str1.startsWith("0")==false) return str1; for(int index=0;index<str1.length();index++){ if(str1.charAt(index)>str2.charAt(index)) return str2; if(str1.charAt(index)<str2.charAt(index)) return str1; } return str1; } }
public String PrintMinNumber(int[] numbers) { List<String> list = new ArrayList<>(); for(int num : numbers) list.add(String.valueOf(num)); Collections.sort(list, (a, b)->((a+b).compareTo(b+a))); StringBuffer sb = new StringBuffer(); for(String s : list){ sb.append(s); } return sb.toString(); }
import java.util.*; import java.util.ArrayList; public class Solution { PriorityQueue<Integer> p=new PriorityQueue<>(new Comparator<Integer>(){ //设置排序规则 /** * 宗旨: 对于两个数字第一个不同的字符,字符代表数字最小的应当排在前面,(贪心思想) * */ @Override public int compare(Integer o1,Integer o2){ char[] oo1=o1.toString().toCharArray(); char[] oo2=o2.toString().toCharArray(); int index1=0,index2=0; while((oo1[index1] == oo2[index2]) && index1!=oo1.length-1 && index2!=oo2.length-1){ if(index1!=oo1.length-1) index1++; if(index2!=oo2.length-1) index2++; } if(index1==oo1.length-1 && index2==oo2.length-1) return oo1[index1]-oo2[index2]; else { if(index1==oo1.length-1){ index1=0; while( index2!=oo2.length-1 && oo1[index1] == oo2[index2]){ index2++; } } else if(index2==oo2.length-1){ index2=0; while(index1!=oo1.length-1 && oo1[index1] == oo2[index2]){ index1++; } } return oo1[index1]-oo2[index2]; } } }); public String PrintMinNumber(int [] numbers) { //将数组中的数放入优先对列 for(int num : numbers){ p.offer(num); } StringBuilder target=new StringBuilder(); //依次取出放入 while(!p.isEmpty()){ target.append(p.poll().toString()); } return target.toString(); } }
public String PrintMinNumber(int[] numbers) { return Arrays.stream(numbers) .mapToObj(String::valueOf) .sorted((s1,s2) -> (s1+s2).compareTo(s2+s1)) .collect(Collectors.joining()); }
import java.util.*; /** * 把数组排成最小的数 * 对于本题,我们要的有效序列是:序列中任何一个元素y,和它前的任何一个元素x进行有序组合形成 xy, * 比和他后面的任何一个元素z进行有效序列组合yz,满足条件xy < yz(采用字典序列排序) * @param numbers * @return */ public class Solution { public String PrintMinNumber(int [] numbers) { if (numbers == null) { return new String(); } ArrayList<Integer> list = new ArrayList<>(); for (int num : numbers) { list.add(num); } Collections.sort(list, new Comparator<Integer>() { @Override public int compare(Integer x, Integer y) { String xs = x + "" + y; String ys = y + "" + x; return xs.compareTo(ys); } }); String result = new String(); for (Integer num : list) { result += num; } return result; } }
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; public class Solution { public String PrintMinNumber(int [] numbers) { String[] strs = new String[numbers.length]; for(int i=0;i<numbers.length;i++){ strs[i] = String.valueOf(numbers[i]); } Arrays.sort(strs,(String s1,String s2)->(s1+s2).compareTo(s2+s1)); StringBuilder ret = new StringBuilder(); for(String s:strs){ ret.append(s); } return ret.toString(); } }
import java.util.*; public class Solution { public String PrintMinNumber(int [] numbers) { // 转化为排序: if(numbers.length==0 || numbers==null) return ""; // 排序规则为:保证A+B < B+A (用哪种排序都行,只要保证排序规则如上就可) for(int i=0;i<numbers.length-1;i++){ for(int j=0;j<numbers.length-i-1;j++){ if(getValue(numbers[j],numbers[j+1])>getValue(numbers[j+1],numbers[j])){ int temp = numbers[j]; numbers[j] = numbers[j+1]; numbers[j+1] = temp; } } } // 转化为String返回 StringBuilder sb = new StringBuilder(); for(int i=0;i<numbers.length;i++){ sb.append(numbers[i]); } return sb.toString(); } public long getValue(int a, int b){ return Long.parseLong(""+a+b); } }
//此题原理看上去有点绕,不过可以换个思路 //考虑n进制,n适当大,就可以把问题简化了,逻辑就简单了 import java.util.*; public class Solution{ public String PrintMinNumber(int[] numbers){ String[] str = new String[numbers.length]; for(int i = 0;i < numbers.length;i++){ str[i] = String.valueOf(numbers[i]); } Arrays.sort(str,(x,y)->(x+y).compareTo(y+x)); String res = ""; for(String s:str){ res +=s; } return res; } }
//用字典序写超时 import java.util.*; import java.math.BigDecimal; public class Solution { public String PrintMinNumber(int [] numbers) { if(numbers.length == 0)return ""; String ans = null; int i,j; Arrays.sort(numbers); StringBuffer temp = new StringBuffer(""); for(j = 0; j<numbers.length;j++)temp.append(numbers[j]); ans = temp.toString(); for(i = numbers.length-2; i >= 0; i--){ if(numbers[i]<numbers[i+1]){ j = numbers.length - 1; while(j>i && numbers[j]<=numbers[i])j--; int t = numbers[i]; numbers[i] = numbers[j]; numbers[j] = t; int x = i+1; int y = numbers.length-1; while(x<y){ t = numbers[x]; numbers[x++] = numbers[y]; numbers[y--] = t; } temp = new StringBuffer(""); for(j = 0; j<numbers.length;j++)temp.append(numbers[j]); if(ans == null)ans = temp.toString(); else { BigDecimal a = new BigDecimal(temp.toString()); BigDecimal b = new BigDecimal(ans); if(a.compareTo(b)<0){ ans = temp.toString(); } } i = numbers.length-1; } } return ans; } }
import java.util.*; public class Solution { public String PrintMinNumber(int[] numbers) { if (numbers == null || numbers.length == 0) { return ""; } Integer[] nums = Arrays.stream(numbers).boxed().toArray(Integer[]::new); Arrays.sort(nums, (o1, o2) -> ("" + o1 + o2).compareTo("" + o2 + o1)); StringBuilder sb = new StringBuilder(); for (int num : nums) { sb.append(num); } return sb.toString(); } }
/* 思路: 把各个数转为字符串,放到list里用Collections进行排序。 小的放到前面,这样排序完后就是结果。 定义compare的规则: 由于每个字符串的长度不同,不能直接比较。 但是可以去比较它们拼接后的字符串(c1=s1+s2.c2=s2+s1) 举个例子,如s1=3,s2=32 c小的要放到前面,也等价于对应的s也要放到前面。 所以return c1.compareTo(c2) s1+s2 s2+s1 (s1+s2).compareTo(s2+s1)是关键 */ public String PrintMinNumber(int [] numbers) { ArrayList<String> list = new ArrayList<>(); for(int i = 0;i < numbers.length;i++){ //int转String,为String的静态方法,String.valueOf() list.add(String.valueOf(numbers[i])); } /* Collections.sort与Arrays.sort的区别: 它们都可以定义comparator。 它们的参数不同,Collections.sort的参数为list, 而Arrays.sort的参数为数组。 可以多用Colections.sort */ //Comparator的包也要导入 Collections.sort(list,new Comparator<String>(){ //c小的放前面,与s的放置规则等价。 @Override public int compare(String s1,String s2){ return (s1+s2).compareTo(s2+s1); } }); StringBuilder sb = new StringBuilder(); for(String item : list){ sb.append(item); } return sb.toString(); }
import java.util.*; public class Solution { public String PrintMinNumber(int[] numbers) { String[] strs = new String[numbers.length]; for(int i = 0; i < numbers.length; i++) { strs[i] = String.valueOf(numbers[i]); } Arrays.sort(strs, new Comparator<String>() { public int compare(String a, String b) { return (a+b).compareTo(b+a); } }); StringBuilder sb = new StringBuilder(); for(int i = 0; i < strs.length; i++) { sb.append(strs[i]); } return sb.toString(); } }
import java.util.*; public class Solution { public String PrintMinNumber(int [] numbers) { String[] strs = new String[numbers.length]; for (int i = 0; i < numbers.length; i++) { strs[i] = String.valueOf(numbers[i]); } Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x)); StringBuilder sb = new StringBuilder(); for (String str : strs) { sb.append(str); } return sb.toString(); } }自定义排序规则,若拼接字符串 x + y < y + x,则 x 在 y 前;
import java.util.stream.Collectors; import java.util.stream.IntStream; public class Solution { public String PrintMinNumber(int[] nums) { return IntStream.of(nums).mapToObj(String::valueOf) .sorted((s1, s2) -> (s1 + s2).compareTo(s2 + s1)) .collect(Collectors.joining()); } }
import java.util.ArrayList; public class Solution { public String PrintMinNumber(int[] numbers) { int max = 0; // 最大位数 // 找出最大位数 for (int i = 0; i < numbers.length; i++) { int temp = numbers[i]; int length = 0; while (temp != 0) { length++; temp /= 10; } if (length > max) { max = length; } } int[] clone = numbers.clone(); // 补齐数位,比如32的个位是2,长度为3,那么我们就需要将其转化成322 for (int i = 0; i < numbers.length; i++) { while (clone[i] /(int) Math.pow(10, max - 1) == 0) { clone[i] = clone[i] * 10 + clone[i] % 10; } } // 构建二维数组集合,第一个位置存clone[i],第二个位置为numbers[i],相当于对应键找值。 ArrayList<int[]> list = new ArrayList<>(); for (int i = 0; i < clone.length; i++) { list.add(new int[]{clone[i],numbers[i]}); } int[] temp = new int[clone.length]; sort(clone, 0, clone.length - 1, temp); StringBuffer buffer = new StringBuffer(); //对应clone找numbers for (int i = 0; i < clone.length; i++) { for (int j = 0; j < list.size(); j++) { if (list.get(j)[0] == clone[i]) { buffer.append(list.get(j)[1]); list.remove(list.get(j)); } } } return buffer.toString(); } //归并排序的实现 private void sort(int[] arr, int left, int right, int[] temp) { int mid = (left + right) / 2; if (left < right) { //记住:这里是if,别再写while了 sort(arr, left, mid, temp); sort(arr, mid + 1, right, temp); mergeSort(arr, left, mid, right, temp); } } private void mergeSort(int[] arr, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int index = left; while (i <= mid && j <= right) { if (arr[i] < arr[j]) { temp[index++] = arr[i++]; } else { temp[index++] = arr[j++]; } } while (i <= mid) { temp[index++] = arr[i++]; } while (j <= right) { temp[index++] = arr[j++]; } while (left <= right) { arr[left] = temp[left++]; } } }看了一下题解:
import java.util.ArrayList; public class Solution { // 思路:按照其他题解,要合理的给numbers排序的话,首先要有合理的排序规则, // 即两数拼接时较小的情况的次序作为他们之间的大小顺序, // 下面是我对归并排序的变式来对这个思路进行优化。 public String PrintMinNumber(int[] numbers) { int[] temp = new int[numbers.length]; diffSort(numbers, 0, numbers.length - 1, temp); StringBuffer buffer = new StringBuffer(); for (int i = 0; i < numbers.length; i++) { buffer.append(numbers[i]); } return buffer.toString(); } private void diffSort(int[] numbers, int left, int right, int[] temp) { int mid = (left + right) / 2; if (left < right) { diffSort(numbers, left, mid, temp); diffSort(numbers, mid + 1, right, temp); diffMergeSort(numbers, left, mid, right, temp); } } private void diffMergeSort(int[] numbers, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int index = left; while (i <= mid && j <= right) { String a = String.valueOf(numbers[i]); String b = String.valueOf(numbers[j]); if (Integer.parseInt(a + b) < Integer.parseInt(b + a)) { temp[index++] = numbers[i++]; } else { temp[index++] = numbers[j++]; } } while (i <= mid) { temp[index++] = numbers[i++]; } while (j <= right) { temp[index++] = numbers[j++]; } while (left <= right) { numbers[left] = temp[left++]; } } }
public class Solution { public String PrintMinNumber(int [] numbers) { //首先要每一次筛选最高项的大小,选出最小的,进行数组的移动 int[] result=new int[numbers.length]; String str=""; //首先获得数组中所有元素的最高位数 int maxbit=0; for(int k=0;k<numbers.length;k++){ int bitnum=getMaxbit(numbers[k]); if(maxbit<bitnum){ maxbit=bitnum; } } int[] poll_array=Polish(numbers,maxbit); int counter=0; for(int m=0;m<poll_array.length;m++){//查到最小的数得到其下标,然后加入到result中 int minindex=0; int minnum=poll_array[0]; for(int n=0;n<poll_array.length;n++){ if(poll_array[n]<minnum){ minnum=poll_array[n]; minindex=n; } } poll_array[minindex]*=10; result[counter]=numbers[minindex];//将获得的结果加入到result中 counter++; } for(int i=0;i<result.length;i++){ str+=result[i]; } return str; } public int getMaxbit(int num){//得到数字的位数 int div=1; int bit=0; while(num/div!=0){ bit++; div*=10; } return bit; } //根据位数,不够位的按最后一位补齐 public int[] Polish(int[] nums,int maxbits){ int[] polishing_array=new int[nums.length]; for(int i=0;i<nums.length;i++){ int numbits=getMaxbit(nums[i]); int tempnum=nums[i]; if(numbits<maxbits){ int lastnum=nums[i]%10; for(int j=numbits;j<maxbits;j++){ tempnum=tempnum*10+lastnum; } } polishing_array[i]=tempnum; } return polishing_array; } }
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
int n;
String s="";
ArrayList<Integer> list= new ArrayList<Integer>();
n=numbers.length;
for(int i=0;i<n;i++){
list.add(numbers[i]);
}
Collections.sort(list, new Comparator<Integer>(){
public int compare(Integer str1,Integer str2){
String s1=str1+""+str2;
String s2=str2+""+str1;
return s1.compareTo(s2);
}
});
for(int j:list){
s+=j;
}
return s;
}
}