当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-68-把数组排成最小的数。一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的。例如输入数组{32, 321},则输出32132

发表于: 2012-03-05   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.Arrays; import java.util.Comparator; public class MinNumFromIntArray { /** * Q68输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。 * 例如输入数组{32, 321},则输出这两个能排成的最小数字32132。请给出解决问题
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;
	}
}

java-68-把数组排成最小的数。一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的。例如输入数组{32, 321},则输出32132

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。 例如输
题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。 例如输
题目: 输入一个正整数数组,把数组里面的所有数字连接起来排成一个数,打印能拼接出的所有数字中最
代码和任务 /*copyright(c)2015 csdn学院 *All right reserved. *文件名称:test.java *作者;张如
#include "stdio.h" #define N 100 void main() { int a[N],i,n; /*定义a[N]存放输入的数值,在C语言
时间限制:1 秒内存限制:32 兆特殊判题:否 题目描述: 把一个数组最开始的若干个元素搬到数组的末
题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增的排序的
惯例,我们来看一下题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输
旋转数组的特点: (1)递增排序的数组旋转之后的数组可划分为两个排序的子数组; (2)前面的子数
/* * Copyright (c) 2013, 烟台大学计算机学院 * All rights reserved. * 作 者:马广明 * 完成日期
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号