import java.util.Arrays;
import java.util.Comparator;
public class MinNumFromIntArray {
/**
* Q68输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。
* 例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题的算法,并证明该算法。
*/
public static void main(String[] args) {
int[][] val={
{32,321},//32132
{532,45,78},//4553278
{2,23,231},//223123
{2,3,1},//123
};
for(int[] x:val){
//solution 1
String result=minNumFromIntArray(x);
System.out.println(result);
//solution 2
AuxClass minStr=new AuxClass();
minNumFromIntArray2(x,0,x.length-1,minStr);
System.out.println(minStr.str);
}
//System.out.println("32".compareTo("321"));//<0
}
/*solution 1:
* if ab<ba,then a<b
* 1.sort the integer array. the comparator is "if ab<ba,then a<b"
* 2.append each integer in the array to create a string and that's the result.
*/
public static String minNumFromIntArray(int[] x){
String[] strs=stringsOf(x);
Arrays.sort(strs,new Comparator<String>(){
public int compare(String o1, String o2) {
return (o1+o2).compareTo(o2+o1);
}
});
StringBuilder sb=new StringBuilder();
for(String each:strs){
sb.append(each);
}
return sb.toString();
}
//int[] to String[].For comparing.
public static String[] stringsOf(int[] x){
int len=x.length;
String[] strs=new String[len];
for(int i=0;i<len;i++){
strs[i]=""+x[i];
}
return strs;
}
/*solution 2
* get all the permutations.
* find the min.
* Of course we use String instead of Big Integer.
*/
public static void minNumFromIntArray2(int[] x,int first,int last,AuxClass minStr){
if(first==last){
StringBuilder sb=new StringBuilder();
for(int each:x){
sb.append(each);
}
if(minStr.str==null){
minStr.str=sb.toString();
}else{
if(minStr.str.compareTo(sb.toString())>0){
minStr.str=sb.toString();
}
}
return;
}
for(int i=first;i<=last;i++){
swap(x,first,i);
minNumFromIntArray2(x,first+1,last,minStr);
swap(x,first,i);
}
}
public static void swap(int[] x,int i,int j){
int temp=x[i];
x[i]=x[j];
x[j]=temp;
}
/*
* when you use 'String' instead of inner class,you get 'null' all the time
*/
static class AuxClass{
String str;
}
}
分享到:
相关推荐
题目描述输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解法一:cmp_to_key函数 from ...
题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。 解题思路一:暴力破解:先求所有...
C语言程序设计-输入一维数组的8个元素,并将最大值与最后一个数交换,最小值与第一个数交换,然后输出交换后的8个数。
指针 ~~编写一个函数,将数组中n个数按反序存放。 实验步骤与要求: 在主函数中输入10个数,并输出排好序的数。 编写函数invert()将10个数按反序存放。
我们使用Python的random模块生成了两个随机数组,分别是1到36中随机选取的5个数和1到12...第二个参数是一个整数,表示要选取的随机元素个数。同时,我们还需要根据实际情况修改代码中的数组范围和选取的随机元素个数。
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;本.cC语言程序设计-
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;请编写fun函数;.c
想了解IO输入输出流的学者可以看看,里面有详细的讲解及源代码。
编写一个程序,允许用户向一个大小为10的数组输入整型值。程序应通过索引,或者通过指定一个大于0的值来查找数字元素,从而获取数组中的值。程序应处理任何在向数组输入数值或访问数组元素时发生的异常。此外,程序...
java代码-使用java输入参数是一个正整数,输出该整数所对应的二进制数对应的字符串的源代码 ——学习参考资料:仅用于个人学习使用!
设有n个正整数,将他们连接成一排,组成一个最大的多位整数。 如:n=3时,3个整数13,312,343,连成的最大整数为34331213。 如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。 输入描述: 有多组测试样例,每组...
TIA博途-整数拆分到字节数组中-全局FC库文件-V15版本
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
桂林电子科技大学计算机与信息安全学院计算机组成原理课程设计,题目为输入包含10个整数(无符号数)的数组M,输出中位数。文件里面有代码,有文档。下载可直接使用。
输入一个数是不是在这个数组中,数组的循环输出
数据结构教程(JAVA语言描述) 求一个含有n个整数元素的数组a[0..n-1]中的最大元素,有这样一种思路:先比较第一个元素,再比较第二个元素,比较过程向中间靠近
第六章 数组 C++除了提供前面已介绍的基本数据类型外,还提供了导出(构造)数据类 型,以满足不同应用的需要。...常量表达式的值为一个正整数,它规定了数 组的元素个数,即数组的大小。如变量说明
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
输入10个整数,将其中最小的数与第一个数对换,把最大的数与最后一个数对换。