1

面接の質問です。正の整数の配列があり、結果の数値がこの配列を使用して形成できる最大数になるように、配列要素を再配置して結合する必要があります。

例えば：

[884 88] -> 88884

[20 19 90] -> 902019

[909 90] -> 90990

私の解決策：最初に要素を最上位桁（MSD）で降順で並べ替えると思いました。

つまり、909、12、88 の場合、ソート後に 909、88、12 になり、同じ MSD を持つ場合は 2 番目の MSD をソートし、これを続けます。

したがって、配列 909, 99 の場合、99 と 909 があり、それらを結合します。しかし、配列 909, 90 の場合、90, 909 になります。両方の数値で共通の 90 があるため、ここに問題があります。

90

909 ---> ここでは2つの組み合わせが可能で、90は共通なので909から共通部分を除いた9が残っているので、90にこの9を追加すると大きくなるかどうかを調べます。この場合、90 の前に 9 を追加すると、909 よりも大きい 990 が得られるため、909 の後に 90 が続きます。したがって、答えは 90990 です。

しかし、コーディングしようとすると、複雑すぎてコーディングが難しいことがわかりました。助言がありますか？

4

4 に答える 4

0

数字のセットでwidth=min（#digits）とします

最初の幅の数字だけで減少する数字を並べ替える-最初に桁数の少ない数字を並べ替えて、関係を解消します

最初のものを取る

繰り返す

于 2013-01-30T18:12:46.820 に答える
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 に答える
0

ここにロジックがあるはずです。両方の数値を連結して比較します。大きい方を取り、逆順に並べ替えます。逆配列はより大きな数を生成します。以下はJavaでのコードです。

public class 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 に答える