Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1504
Question Name: Sort Array For Min Number
Question Description: Given an integer array, concatenate them as in their string representation, and find out the minimum one among the concatenated results.
Input: the input might contain multiple test cases. Each test case contains two lines. The first line includes one integers N (1<= N <=100), saying the size of test array. The second line includes N integers (0 <= each item <= 10000000), as the content of the test array.
Output: For each test case, print the minimum concatenated result.
1 2 3 4 5 6 7 8 9 10 11 | Input: 3 23 13 6 2 23456 56 2 35 351 Output: 13236 2345656 35135 |
The solution is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | /*---------------------------------------------------------------- * Author: Sheng Yu codesays.com * Written: 08/31/2014 * Last updated: 08/31/2014 * * Filename: SortArrayForMinNumber.java * Compilation: javac SortArrayForMinNumber.java * Execution: java SortArrayForMinNumber * JDK Used: 1.7 *----------------------------------------------------------------*/ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; import java.util.Comparator; /** * Given an array of integers, concatenate them as strings to generate * the minimum result. * @author Sheng Yu codesays.com */ public class SortArrayForMinNumber { /** * Concatenate the integers in input as in their string representation, * to generate the minimum possible result. * @param input the integers to concatenate. * @return the minimum numbers from concatenating the integers. */ public String generateMin(int[] input) { // Convert the input into strings. String[] strInput = new String[input.length]; for (int i = 0; i < input.length; ++i) { strInput[i] = Integer.toString(input[i]); } // Sort the strings Arrays.sort(strInput, new Comparator<String>() { public int compare(String o1, String o2) { return (o1 + o2).compareTo(o2 + o1); } } ); // Concatenate the strings, representing the integers. StringBuilder sb = new StringBuilder(); for (String str : strInput) sb.append(str); return sb.toString(); } /** * Stub for test. * @param args the command line arguments. * @throws IOException when input gets error. */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); int inputSize = 0; int[] input = null; SortArrayForMinNumber generator = new SortArrayForMinNumber(); while (st.nextToken() != StreamTokenizer.TT_EOF) { inputSize = (int) st.nval; input = new int[inputSize]; while (inputSize-- > 0) { st.nextToken(); input[inputSize] = (int) st.nval; } System.out.println(generator.generateMin(input)); } } } |