2

与えられA[1..n]た：実数 の配列。

目標D[1..n]：次のような配列

D[i] = min{ distance(i,j) : A[j] > A[i] }

または、より高い値の要素がない場合は、デフォルト値（0など）。ここでは本当にユークリッド距離を使いたいと思います。

例：

A = [-1.35, 3.03, 0.73, -0.06, 0.71, -0.21, -0.12, 1.49, 1.41, 1.42]
D = [1, 0, 1, 1, 2, 1, 1, 6, 1, 2]

n明らかなO（ ^ 2）ソリューションを打ち負かす方法はありますか？私がこれまでに成し遂げた唯一の進歩は、D[i] = 1いつでもA[i]極大ではないということです。私はよく考えていて、何も思いつきませんでした。最終的にこれを2Dに拡張したいと思っています（つまりA、D行列です）。

4

2 に答える 2

1

だから私はこれについて少し戸惑いましたが、うまくいくものは何も思いつきませんでした. いくつかのアイデア:

  • O(n) 時間またはそれ以上で取得できる追加情報で配列を拡張します。たとえば、インデックスを追加したり、近隣間の差などを追加したりします。
  • ソート (O(n(log n))) は何らかの形で役立ちますか?
  • 隣接する要素の解に基づいて各要素を解く方法を見つけることができれば、ここでは動的計画法が役立つようです (単に距離ではなく、 jfor eachのような情報で答えを補強します)。A[i]
于 2010-04-01T14:23:43.460 に答える
0

配列を最も高い要素から最も低い要素に並べ替えます。私があなたの問題を正しく理解していれば、元のリストの任意の要素に最も近い大きな要素がその前の要素であるため、これですぐに答えが得られます。この方法では、D []配列を作成する必要はありません。これは、その内容の計算が配列A[]のみを使用して実行できるためです。ソートされたA[]配列の最初の要素には大きな友達がいないため、その答えはデフォルトのvalye（おそらく0？）になります。行列のアルゴリズムを拡張するのは簡単かもしれません（行列を「見る」方法によって異なります）。行列を1D配列に変換するマッピング関数を使用するだけです。

于 2010-05-27T06:01:07.480 に答える