四个任意位数值组合最大数求解的程序实现

Question

假设有四个任意数 234, 345, 46, 1345，它们组合成的最大数是 46 345 234 1345；

这个简单，先取首位数值最大的那个数放在最前面，依次即可。

假设有四个任意数 234, 345, 46, 2345，它们组合成的最大数是 46 345 2345 234；

这个就需要进行不同数值内部每一位位的比较。

如此，该如何用程序具体地求解实现呢？

Answer 1

感谢@xiaoyifang提醒，之前的思路有问题。

这个题目核心在于两个数字串之间如何比较
通常思路是比较拼接后的串哪个大。即比较[串1拼串2] 和 [串2拼串1]的大小，从而决定哪个在前。
可以用循环指针的做法节省空间开销：
用两个指针分别指向串1串2的起始位置，不断右移比较。串的指针到尾部时循环回头部继续比对，直到满足return条件(两指针对应的char不等)或循环次数达到两串长度之和结束。

public static String maxCombine(String[] input) {
    Arrays.sort(input, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            for(int i = 0; i < o1.length() + o2.length(); i++) {
                char p1 = o1.charAt(i % o1.length());
                char p2 = o2.charAt(i % o2.length());
                if(p1 != p2) return p2 - p1;
            }
            return 0;
        }
    });

    String result = "";
    for(String s : input) {
        result += s + " ";
    }
    return result;
}

public static void main(String[] args) {
    String[] test = {"7347", "734"};
    System.out.println(maxCombine(test));
}

Answer 2

int _tmain(int argc, _TCHAR* argv[])
{
    string arr[] = { "234", "345", "46", "2342" };
    string arr2[] = { "1", "2", "10", "11", "110" };

    sort(begin(arr2), end(arr2), [](string const & left, string const & right)
    {
        string l = left + right;
        string r = right + left;

        return l > r;
    });


    for (auto i : arr2)
    {
        cout << i << " ";
    }

    return 0;
}

隐含的问题是当两个字符串的起始都是一样的，并且一个字串是另一个字串的子串时，该如何排放这两个字符串的先后顺序。