正の整数の配列が与えられた場合、整数のa配列を出力したいbのでb[i]、最も近い数値a[i]は よりも小さく、a[i]になり{a[0], ... a[i-1]}ます。そのような番号が存在しない場合は、b[i] = -1.
例：
a = 2 1 7 5 7 9 b = -1 -1 2 2 5 7
b[0] = -12 より小さい数は
b[1] = -1ないので から 1 より小さい数はないので から{2}
b[2] = 27 より小さい 7に最も近い数{2,1}は 2
b[3] = 2から 5 より小さい 5に最も近い数{2,1,7}は 2 から 2
b[4] = 5より近い数から 7 より小さい 7 から{2,1,7,5}は 5
バランスの取れた二分木を実装することを考えていましたが、多くの作業が必要になります。これを行う簡単な方法はありますか？
1 つのアプローチを次に示します。
for i ← 1 to i ← (length(A)-1) {
// A[i] is added in the sorted sequence A[0, .. i-1] save A[i] to make a hole at index j
item = A[i]
j = i
// keep moving the hole to next smaller index until A[j - 1] is <= item
while j > 0 and A[j - 1] > item {
A[j] = A[j - 1] // move hole to next smaller index
j = j - 1
}
A[j] = item // put item in the hole
// if there are elements to the left of A[j] in sorted sequence A[0, .. i-1], then store it in b
// TODO : run loop so that duplicate entries wont hamper results
if j > 1
b[i] = A[j-1]
else
b[1] = -1;
}
ドライラン:
a = 2 1 7 5 7 9
a[1] = 2
b[1]-1に設定された簡単な方法
a[2] = 1
サブ配列に挿入:[1 ,2]
ソートされた配列の 1 より前の要素はありますか? 番号。したがってb[2]、 -1 に設定します。b: [-1, -1]
a[3] = 7
サブ配列に挿入:[1 ,2, 7]
ソートされた配列内の 7 より前の要素はありますか? はい。その 2 だから 2 に設定b[3]します。 b: [-1, -1, 2]
a[4] = 5
サブ配列に挿入:[1 ,2, 5, 7]
ソートされた配列の 5 より前の要素はありますか? はい。その 2 だから 2 に設定b[4]します。 b: [-1, -1, 2, 2]
等々..
あなたはそれを挿入ソートのように扱うことができます。
擬似コード：
let arr be one array with enough space for every item in a
let b be another array with, again, enough space for all elements in a
For each item in a:
perform insertion sort on item into arr
After performing the insertion, if there exists a number to the left, append that to b.
Otherwise, append -1 to b
return b
心配しなければならない主なことは、配列の再割り当てを間違えないようにすることです（n回再割り当てされるため、非常にコストがかかります）。これは、使用する言語の実装の詳細になります（std ::vectorのC++用リザーブ...arr.reserve（n）for D ...ArrayListのJavaでのensureCapacity...）
二分木を使用する場合と比較して、このアプローチの潜在的な欠点は、O（n ^ 2）時間であるということです。ただし、この方法と二分木を使用する定数係数は、サイズが小さい場合にこれを高速化します。nが1000より小さい場合、これは適切な解決策になります。ただし、O（n log n）の成長はO（n ^ 2）よりもはるかに遅いため、のサイズが大幅に大きくなると予想され、違反する可能性のある時間制限がある場合は、より複雑なO（ n log n）アルゴリズム。
パフォーマンスをわずかに向上させる方法はありますが（バイナリ挿入ソートを使用する：バイナリ検索を使用して挿入する位置を見つけるなど）、通常はまだO（n ^）であるため、ほとんどの場合、パフォーマンスを十分に向上させることはできません。 2）要素をシフトしてフィットさせる時間。
これは、挿入ソートとバランスの取れたバイナリ ツリーの実装の難しさの中間に位置する (ほぼ) O(n log n) アルゴリズムのスケッチです。
擬似コード:
let c be a copy of a
let b be an array sized the same as a
sort c using an O(n log n) algorithm
for i from a.length-1 to 1
binary search over c for key a[i] // O(log n) time
remove the item found // Could take O(n) time
if there exists an item to the left of that position, b[i] = that item
otherwise, b[i] = -1
b[0] = -1
return b
これを実行時に貧弱にする可能性のある実装の詳細がいくつかあります。
たとえば、アイテムを削除する必要があるため、通常の配列でこれを実行して物事をシフトすると、このアルゴリズムにはまだ O(n^2) 時間がかかります。そのため、代わりにキーと値のペアを保存できます。1 つはキーで、もう 1 つはそれらのキーの数です (配列に実装されたマルチセットのようなものです)。1つを「削除」すると、ペアから2番目のアイテムが差し引かれます。
最終的には、値が 0 のキーがたくさん残ることになります。これにより、最終的にはif there exists an item to the leftおおよそ O(n) 時間かかり、そのため、アルゴリズム全体が O(n^2) に低下します。したがって、別の最適化は、それらすべてを定期的にバッチ削除することです。たとえば、そのうちの 1/2 が 0 値の場合、枝刈りを実行します。
理想的なオプションは、削除時間がはるかに有利な別のデータ構造を実装することです。インデックス付きの変更された展開されたリンク リストの行に沿った何かが機能する可能性がありますが、このアプローチの実装の複雑さが確実に増加します。
私は実際にこれを実装しました。上記の最初の 2 つの最適化を使用しました (圧縮のためにキーと値のペアを保存し、それらの 1/2 が 0 の場合はプルーニングします)。挿入ソートの派生物を使用してこれと比較するためのベンチマークを次に示します。
a.length このメソッド Insert sort メソッド 100 0.0262ms 0.0204ms 1000 0.2300ms 0.8793ms 10000 2.7303ms 75.7155ms 100000 32.6601ms 7740.36ms 300000 98.9956ms 69523.6ms 1000000 333.501 ミリ秒????? 我慢が足りない
ご覧のとおり、このアルゴリズムは、以前に投稿した挿入ソート方法よりもはるかにゆっくりと成長します。ただし、73 行のコードが必要だったのに対し、挿入ソート メソッドでは 26 行のコードが必要でした。したがって、単純さの観点から、時間要件がない場合/入力が小さい場合は、挿入ソート方法が依然として適している可能性があります。
このことを考慮：
a = 2 1 7 5 7 9
b = -1 -1 2 2 5 7
c 0 1 2 3 4 5 6 7 8 9
0 - - - - - - - - - -
ここで、Cのインデックスはa [i]の値であり、0、3、4、6、8はnull値になります。
Cの1次元には、a[i]に最も近い日付の最高値が含まれます。
So in step by a[3] we have the following
c 0 1 2 3 4 5 6 7 8 9
0 - -1 -1 - - 2 - 2 - -
and by step a[5] we have the following
c 0 1 2 3 4 5 6 7 8 9
0 - -1 -1 - - 2 - 5 - 7
このようにして、a[4]で2番目の7に到達すると、2がこれまでで最大の値であることがわかり、必要なのは、a[i-1]をループバックしてa[を比較する7に再び遭遇することです。 i] c [7]の値よりも大きい場合は、c[7]を置き換えます。a [i-1] = 7になったら、c[7]をb[i]に入れ、次のa[i]に進みます。
私が見ることができるこのアプローチの主な欠点は次のとおりです。