1

这是一道面试题。我们有一个正整数数组，我们必须重新排列和连接数组元素，以使结果数是使用该数组可以形成的最大数。

例如：

[884 88] -> 88884

[20 19 90] -> 902019

[909 90] -> 90990

我的解决方案：我认为首先按最重要的数字（MSD）按降序对元素进行排序。

即对于 909 , 12, 88 ，我们将在排序后获得 909, 88, 12 ，对于具有相同 MSD 的那些排序第二个 MSD 并继续这样做。

因此，对于数组 909、99，我们将拥有 99 和 909 并将它们组合起来。但是对于数组 909、90，我们将有 90、909，这是一个问题，因为我们在两个数字中都有 90，所以

90

909 ---> 这里可能有两种组合，因为 90 是常见的，所以从 909 中删除公共部分后留下 9，所以我会检查将这个 9 附加到 90 是否使其变大。在这种情况下，在 90 前面加上 9，我们得到 990，它大于 909，所以 909 后面跟着 90。所以答案是 90990。

但是当我尝试对其进行编码时，我发现由于涉及太多复杂性而难以编码。有什么建议么？

4

4 回答 4

0

这只是一个基数排序问题。需要按降序对数字进行排序。然后生成号码。

于 2013-11-15T11:30:27.563 回答
0

让宽度 = min(#digits) 在数字集中

仅对按第一个宽度数字递减的数字进行排序 - 通过首先对具有较少数字的数字进行排序来打破平局

拿第一个

重复

于 2013-01-30T18:12:46.820 回答
0

这里的逻辑应该是。连接两个数字并进行比较。取较大的一个并按照逆序对其进行排序。然后反转的数组将产生更大的数字。以下是java中的代码。

公共类 ArrangeToFormBiggerNumber { /** * @param args */

public static void main(String[] args)
{
    Integer arr[] = {10,9,20};
    Arrays.sort(arr, new Comparator<Object>()
    {

        @Override
        public int compare(Object o1, Object o2)
        {
            return -(o1 + "" + o2).compareTo(o2 + "" + o1);
        }

    });
    String res = "";
    for (Integer i : arr)
    {
        res += i;
    }
    System.out.println(res);
}
}
于 2013-11-15T07:36:28.640 回答
0

我们必须做一个字典排序来解决这个问题。假设I1和I2是我们必须比较的整数，然后取I1+I2和I2+I1，如果I1+I2 > I2+I1，则I1应该放在I2之前，反之亦然。这是这个问题的Java实现。

import java.util.Arrays;
import java.util.Comparator;
public class LexicographicSort implements Comparator<Integer> {

public int compare(Integer o1, Integer o2) {
    String s1 = o1.toString();
    String s2 = o2.toString();
    return (s2+s1).compareTo(s1+s2);
}

public static void main(String[] args) {
    LexicographicSort ls = new LexicographicSort();
    Integer[] nums = {9,1,90,907,5};
    Arrays.sort(nums, ls);
    System.out.println(Arrays.toString(nums));
}
于 2015-10-25T19:41:28.020 回答