在Java中，如何找到给定非负数数组的最大可能数 [英] How to find the largest possible number given an array of non-negative numbers in Java

问题描述

问题陈述：
我在Java中有一个字符串形式的非负数数组，我想将整数排列成最大可能数。

Problem Statement: I have an array of non-negative numbers in form of String in Java, I want to arrange the integers to form the largest possible number.

示例：在下面的输入中给出：

Example: Given below input:

String[] numbers = {"15", "9", "62", "34"};

排列 9623415给出的数字最大。

The arrangement "9623415" gives the largest number.

注意：，我了解我们可以按降序对所有数字进行排序，但简单地排序是行不通的。例如，自然顺序中的15大于9，但是在解决方案中 9在 15之前。在这种情况下，实现自定义比较器的最佳方法是什么？

Note: I understand we can sort all numbers in descending order, but simply sorting doesn’t work. For example, 15 is larger than 9 in natural order but "9" comes before "15" in the solution. What's the best way to implement a custom comparator in this case?

任何帮助将不胜感激。

推荐答案

String 的方法 public int compareTo（String anotherString）需要，您可以按字符串顺序按字典顺序。

the method public int compareTo(String anotherString) of a String is what you need which gives you the order of the String lexicographically .

Update1：​​
什么是字典顺序

Update1: What is lexicographic ordering.

Frome Java Doc：

Frome Java Doc:

这是字典顺序的定义。如果两个字符串不同，则它们要么在某个索引处具有不同的字符（这是两个字符串的有效索引），要么它们的长度不同，或者两者都存在。如果它们在一个或多个索引位置具有不同的字符，则令k为最小索引；则字符串的位置k处的值较小，这是使用<运算符，按字典顺序在另一个字符串之前。在这种情况下，compareTo返回两个字符串中位置k处两个字符值的差，即值：

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）

this.charAt(k)-anotherString.charAt(k)

如果在索引位置上没有区别，则较短的字符串在字典上在较长的字符串之前。在这种情况下，compareTo返回字符串长度的差-即值：

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（）

this.length()-anotherString.length()

因此字符串 9 将出现在字符串 15之前/ code>以字典顺序排序，因为它们在索引 0 处具有不同的字符，而char 9 为大于char 1 。如果您仔细阅读了词典顺序，您会发现该顺序正是OP所需要的！

So String 9will appear ahead of String 15 in a lexicographic ordering, since they have different characters at index 0, and char 9 is larger than char 1. If you read about lexicographic ordering carefully you will find that that order is just what the OP needs!

Update2：为什么词典顺序是关键对于这个问题

Update2: Why lexicographic ordering is the key for this question

问题中字符串的字典顺序如下：

The lexicographic order of the Strings in the question is like this:

9， 62， 34， 15

因此，获得此订单后，问题应该是trival：只需迭代排序的序列，就可以得到答案。

So after you get this order, the question should be trival: just iterate the ordered sequence and you get the answer.

更新3：如何处理特殊情况，例如： 9& 90 ，因为我们需要 990 而不是 909

Update 3: How to handle special case like: "9"&"90", since we need "990" instead of "909"

在这种情况下，字典顺序将失败。但是很容易找出解决办法：

In this case the lexicographic ordering will fail. But it is easy to figure out a fix:

我们可以使用 str1.compareTo（str2）代替（str2 + str1）.compareTo（str1 + str2）。此处的关键是确保这两个字符串至少具有一些不同的数字，因此我们不能通过比较那里的长度来获得顺序。

Instead of str1.compareTo(str2), we can use (str2+str1).compareTo(str1+str2). The key here is to ensure these two strings have at least a bit of different digit, so we don't get the order by comparing there lengths.

这篇关于在Java中，如何找到给定非负数数组的最大可能数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！