-1

各数字の数字が繰り返されないように、2つの整数の間の数字のリストを見つけるアルゴリズムを探していますか？

たとえば、2と12の入力が与えられた場合、答えは11を除くすべての数字になります。単純な解決策は、数字を繰り返し処理し、数字が繰り返されるかどうかを確認することです。ただし、多数の場合、このアプローチには膨大な時間がかかります。

与えられた2つの大きな番号の間のそのような番号の数を見つける必要があります。私が考えたもう1つの方法は、サイズ10の配列（a [10]）を使用することでした。ここで、各インデックスは、特定の番号の各桁の頻度を格納します。b / w制限、およびfreqが1を超えるインデックスを取得した場合、そのインデックスは破棄されません。配列'a'のインデックスを0に初期化するたびに、制限間のすべての番号に対してこれを繰り返します。ただし、この方法でも、大きな入力（制限が1〜10 ^ 9の場合など）では膨大な計算時間がかかります。 。さらに良い方法が必要です。

4

2 に答える 2

4

私はあなたに正確な解決策を与えることはしませんが、同様の問題に取り組む方法についてあなたにいくつかのヒントを与えることを試みます。

まず第一に、このタイプの問題があるときはいつでも、その間の数の数を見つけてaください。与えられたxbの区間の答えを与えるソリューションを実装する方が（ほとんど）常に簡単です。(0, x]たとえば、区間内の数をカウントする必要があり、すべての非負のx[a,b]の区間の答えを返す関数を実装する場合（たとえば、関数は）、の答えをとして計算できます。これにより、多くのコーナーケースのチェックが節約され、通常は実装が高速になります。(0,x]f[a,b]f(b) - f(a - 1)

これを言ったので、間隔に繰り返し桁がない数を数える方法を考えてみてください(0,a]。私が提案するのは、固定桁数の数値の答えを個別に計算することです。桁数が少ない数値の場合、これは非常に簡単です。単純にバリエーションを計算します。桁数が私たちの数に等しい数の場合、それは少しトリッキーです。動的計画法を使用してそれらを数えるのが最も簡単だと思います。

これがお役に立てば幸いです。また、詳細すぎないようにして、自分で何かを解決する必要があることを願っています。

于 2012-11-03T18:51:32.767 に答える
0

あなたは数字の順列を数えるアルゴリズムを探しています。m桁の整数Aとn桁の整数B（m> = n）が与えられた場合、次のことを行う必要があります。

1. for i = m; i < n; i++
    if i < 10, choose i digits out of 10
    Permutate through digits of length i (if i=m, discard permutations that are less than A)

2. Permutate digits of length n, as long as result isn't larger than B.

選択と順列は組み合わせ操作であり、それらの数式を簡単に見つけることができます（再帰バージョンも利用可能です）。たとえば、順列を説明するリンクは次のとおりです。http: //en.wikipedia.org/wiki/Permutation

複雑さはO（（n + 1）！）になります

于 2012-11-03T19:04:21.853 に答える