问题陈述:
我在 Java 中有一个 String 形式的非负数数组,我想排列整数以形成最大可能的数。
示例:给出以下输入:
String[] numbers = {"15", "9", "62", "34"};
排列“9623415”给出的数字最大。
注意:我知道我们可以按降序对所有数字进行排序,但简单排序是行不通的。例如,15 在自然顺序中大于 9,但在解决方案中“9”排在“15”之前。在这种情况下,实现自定义比较器的最佳方式是什么?
如有任何帮助,我们将不胜感激。
String
的方法 public int compareTo(String anotherString)
是您所需要的,它为您提供了 String 字典顺序 的顺序。
更新 1:
什么是字典顺序。
Frome Java 文档:
This is the definition of lexicographic ordering. If two strings are different, then either they have different characters at some index that is a valid index for both strings, or their lengths are different, or both. If they have different characters at one or more index positions, let k be the smallest such index; then the string whose character at position k has the smaller value, as determined by using the < operator, lexicographically precedes the other string. In this case, compareTo returns the difference of the two character values at position k in the two string -- that is, the value:
this.charAt(k)-anotherString.charAt(k)
If there is no index position at which they differ, then the shorter string lexicographically precedes the longer string. In this case, compareTo returns the difference of the lengths of the strings -- that is, the value:
this.length()-anotherString.length()
因此字符串 9
将在字典顺序中出现在字符串 15
之前,因为它们在索引 0
处有不同的字符,而 char 9
大于 char 1
。如果您仔细阅读有关字典顺序的内容,您会发现该顺序正是 OP 所需要的!
更新2:为什么字典顺序是这道题的关键
题目中String的字典顺序是这样的:
"9", "62", "34","15"
所以在你得到这个顺序之后,问题应该是微不足道的:只需迭代有序序列就可以得到答案。
更新 3: 如何处理特殊情况,例如:"9"&"90"
,因为我们需要 "990"
而不是“909”
在这种情况下,字典顺序将失败。但是很容易找出解决方法:
代替str1.compareTo(str2)
,我们可以使用(str2+str1).compareTo(str1+str2)
。这里的关键是确保这两个字符串至少有一点不同的数字,所以我们不会通过比较那里的长度来获得顺序。