1

以下を入力として受け取るアルゴリズムを実装するように依頼されました。

-整数 a のソートされた配列、たとえば a=[0,0,0,0,0,2,4,4,4,4,4]。それが役立つ場合、実際の入力は2つの配列として与えられ、最初の配列は整数を与え、2番目の配列は最初の各整数が現れる回数を与えます。この例では [0,2,4],[5,1,5] です。

-整数 k。

そして、連続する要素が少なくとも k で最大差 |a[i]-b[i]| 異なる一意の実数 (2 桁の 10 進数) の配列 b を返します。可能な限り最小限です。配列 a と b の両方がソートされます。

これまでのところ、前述のように、指定された 2 つの配列を 1 つに変換しました。いくつかのループの後、次の手順に従って、一意の要素を持つ並べ替えられた配列である配列 a を作成しました。

-整数が複数出現するたびに、たとえば 0 を 5 回、それらを可能な限り最小の距離だけシフトします。たとえば、k=2 とすると [0,0,0,0,0]->[-4,-2,0, 2,4]。

-次に、配列を並べ替えて、シフトによって発生した複数の外観を見つけます。

-配列に一意の要素のみが含まれるまで、これらの 2 つの手順を繰り返します。最後の配列の要素を要求された位置に移動する方法があった場合 (したがって、最終的な違いは >=k でした) 、後の配列と開始配列の違いは、要求されたシフトによるものだと思います。

私の考え全体が間違っているか遅すぎるかもしれませんが、私はこの問題で行き止まりに達したので、どんな助けも素晴らしいでしょう!! 前もって感謝します !!!

PS私は全体をより明確にするために演習の小さな例を含めます: K=2, a=[0,1], b=[3,1] (->c= [0,0,0,1] ) したがって、結果は [-2,5 , -0,5 , 1,5 , 2,5] になり、最大最小シフトは 2,50 になります。

4

1 に答える 1

0

の場合max-min <= k*n、配列b

M+0, M+k, M+2k, ..., M+(n-1)k

どこでM満足するか

|max-M-k(n-1)| = |min-M|. 

a連続する配列b要素が異なりk、この場合、最適な結果を得るために必要である限り、心配する必要があるのは配列の最初と最後の要素だけです。

max-min > k*nそれがはるかに簡単な場合:設定

k=(max-min)/(n-1)  

あなたの条件とセットの10進数を満たすb[0]=minkの次のすべての要素に追加しbます。

于 2012-11-23T03:48:45.763 に答える