找到数字的顺序,它将给出数组中最大的数字

Question

让我们说我有一个数组:

int[] arr = {23, 4, 46, 720, 56};

我怎样才能找到能给出最大数字的数字顺序？

例如,在数组arr中,顺序是

7205646423

编辑:也可以有n位数字,即不一定限于3.

例如.,

int[] arr = {223, 23, 72, 7, 64, 9};

答案是

97726423223

Answer 1

词典排序是一个良好的开端.

然而,当考虑到[854, 854853, 854855]需要进行排序时,难以进入[854855, 854, 854853].

解决此问题的一种方法是定义一个比较器,用于比较数字的连接版本(即比较abc和def转换为比较abcdef和defabc).

最简单的版本:

// processing numbers as strings
List<String> array = Arrays.asList("854", "854853", "854855");
Collections.sort(array, new Comparator<String>() {
   @Override
   public int compare(String o1, String o2)
   {
      // negative since we want biggest first
      return -(o1+o2).compareTo(o2+o1);
   }
});

试验.

该compare函数没有实际必须连接数字的开销,只是在原地进行检查:

@Override
public int compare(String s1, String s2)
{
   int i;
   int length = s1.length() + s2.length();
   for (i = 0; i < length; i++)
   {
      char c1 = get(s1, s2, i),
           c2 = get(s2, s1, i);
      if (c1 != c2)
      {
         return (c1 > c2 ? -1 : 1);
      }
   }
   return 0;
}

private char get(String s1, String s2, int index)
{
   if (index < s1.length())
      return s1.charAt(index);
   else
      return s2.charAt(index - s1.length());
}

试验.

我原本有一个更复杂的版本,理论上应该更快一点,因为它有一些for循环,索引环绕到另一个数组,而不是一个循环,检查长度,但简单性击败性能差异为我在这里.如果您有兴趣,请随时查看帖子历史记录(第3版),但请注意该版本有一个错误 - 在最后一个循环之后,另一个索引应该包装到另一个数组中.