在这种情况下，存在已知的算法问题，给定数字数组，例如[1, 20, 3, 14]以最大可能的方式排列数字320141。
使用以下算法，SO和其他站点上有很多解决方案：
String[] strs = new String[nums.length];
for(int i=0; i<nums.length; i++){
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, new Comparator<String>(){
public int compare(String s1, String s2){
String leftRight = s1+s2;
String rightLeft = s2+s1;
return -leftRight.compareTo(rightLeft);
}
});
StringBuilder sb = new StringBuilder();
for(String s: strs){
sb.append(s);
}
return sb.toString();
当然可以，但是我找不到该算法的正式证明。关于quora有一个答案，但我不会称其为正式证明。
谁能给我一个草图或参考一些书或文章？如何从原始问题中获得这一解决方案？
PS我试图解决原始问题，但是我的解决方案是错误的，我无法正确解决，现在我无法完全理解解决方案。
关于表示法：我将使用管道将数字分开，以便更容易同时查看数字序列和所得数字：3 | 20 | 14 | 1
现在，让我们假设由compare函数定义的关系（由运算符表示的R）<=是一个总阶。由表达式确定
-(a+b).compareTo(b+a)
直观地说，如果我们有两个数字a和b，且b | a大于a | b，则b的等级应高于a，即它应出现在解决方案中a的左侧。如果a | b大于b | a，则相反。如果a | b = b | a，则顺序无关紧要。
需要注意的重要一件事是，这种关系不仅影响孤立考虑的两个数字a和b，而且还告诉我们有关两个数字所嵌入的结果数字的一些信息：
如果a <= b，则x | a | b | y <= x | b | a | y
其中x和y是任意长度的数字。换句话说：如果我们有一个数字序列，并且将两个相邻的数字a和b交换为a <= b，那么之后的结果数将更大或相等。
示例：3 | 14 | 20 | 1 <= 3 | 20 | 14 | 1，因为14 <= 20
现在，我们可以得出这样的假设：解不是关系R所暗示的解：一个矛盾：让我们假定解是不符合R的特定序列。由于- [R是一个总的次序，我们可以重新排列数字来匹配ř通过交换相邻的元件，直至该命令符合ř。可以将这种重新排序与冒泡排序进行比较。但是，在每次导致我们获得新订单的交换操作中，结果数都会增加！这显然是矛盾的，因此原始顺序不能成为解决方案。
剩下要说明的是R是一个总阶，即它是传递的，反对称的和总的。由于您要求提供证明的草图，因此我将省略此部分。基本部分是证明可传递性，即
a <= b和b <= c表示a <= c。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句