编程题之数串

题目描述 设有n个正整数，将他们连接成一排，组成一个最大的多位整数。 如:n=3时，3个整数13,312,343,连成的最大整数为34331213。 如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。 输入描述: 有多组测试样例，每组测试样例包含两行，第一行为一个整数N（N<=100），第二行包含N个数(每个数不超过1000，空格分开)。 输出描述: 每组数据输出一个表示最大的整数。

示例1
输入

2
12 123
4
7 13 4 246
输出

12312
7424613

解答

首先，本题可以理解为对N个数进行排序，只不过排序的标准不是数值的大小，而是两个字符串组合到一起转化成整形后的数值大小，所以只需要随便采用一种排序方法，在比较大小时改成比较字符串组合的大小就行。 话不多说，上代码：

import java.util.Scanner;

/**
 * Created by kevin on 17-9-5.
 * Mail: chewenkaich@gmail.com
 */
public class Main {

    public static void main(String[] args) {
        // 获取输入
        Scanner in = new Scanner(System.in);
        int count = Integer.valueOf(in.nextLine().trim());
        if (count > 100) return;
        String inStr = in.nextLine().trim();
        String[] dataStr = inStr.split(" ");
        int[] data = new int[dataStr.length];
        for (int i = 0; i < dataStr.length; i++) {
            data[i] = Integer.valueOf(dataStr[i]);
        }

        // 此处为一个冒泡排序，也可以使用其他快排，归并等其他高效排序方法
        for (int pass = data.length - 1; pass >= 0; pass--) {
            for (int i = 0; i < pass; i++) {
                if (!is1stBiggerThan2nd(data[i], data[i + 1])) { // 第i个数“小于”第i+1个数
                    int tem = data[i + 1];
                    data[i + 1] = data[i];
                    data[i] = tem;
                }
            }
        }

        // 输出结果
        String result = "";
        for (int each : data) {
            result += String.valueOf(each);
        }
        System.out.println(result);
    }

    /**
     * 从两个整数组合起来较大时，其中的第一个整数，例如，
     * a=3489, b=3423
     * 因为a组合b = 34893423 > b组合a = 34233489，所以返回a
     *
     * @param a
     * @param b
     * @return true, a+b > b+a; false, a+b < b+a
     */
    static boolean is1stBiggerThan2nd(Integer a, Integer b) {
        if (Integer.valueOf(String.valueOf(a) + String.valueOf(b)) > Integer.valueOf(String.valueOf(b) + String.valueOf(a)))
            return true;
        else return false;
    }
}

最终程序运行结果如下 运行时间：169ms 占用内存：13040k 如果有任何问题，欢迎指正。