対応する値をすばやく取得する方法

PHP インデックス配列。配列内の値は 1 から 100 までの整数 (非反復) であり、値は断続的になる可能性があります。つまり、7、9 は存在するが、8 は存在しない可能性があります。そして順序が乱れている、つまり1から100まで整っていません

$a=50 と仮定すると、==$a または $a に最も近い 2 つの値を素早く取り出すにはどうすればよいでしょうか?

ちなみに、配列内の値は必ずしも$aと一致するとは限りません

返信内容:

PHP インデックス配列。配列内の値は 1 から 100 までの整数 (非反復) であり、値は断続的になる可能性があります。つまり、7、9 は存在するが、8 は存在しない可能性があります。そして順序が乱れている、つまり1から100まで整っていません

$a=50 と仮定すると、==$a または $a に最も近い 2 つの値を素早く取り出すにはどうすればよいでしょうか?

ちなみに、配列内の値は必ずしも$aと一致するとは限りません

1. array_search — 配列内の指定された値を検索し、成功した場合は対応するキーを返します

2. キーの名前を取得します、$arr[$key-1], $arr[$key+1]それだけです

上記は非常に単純ですが、番号が見つからない場合は、元の配列の順序がバラバラなので、必ずしも上位と下位が最も近いものを見つけます。 もちろん、二分探索も同様です。アイデアとして、私自身のアルゴリズムのアイデアを提供します。私のアイデアは、まずバレルソート (私が現在知っている正の整数をソートする最速の方法) を使用することです。 リーリー

これがどれほど効率的かわかりません

リーリー

変更なしの静的クエリ

• 並べ替え (昇順)、複雑さ nlogn (1 つの並べ替え)

• 次に、2 点による高速位置決め、複雑さのログ (1 つのクエリ)

リーリー

順序を変更せずに追加操作のみを行う動的クエリ

1-100 には 100 個の数字があり、その値も 1-100 です。69 の位置の添字を求める場合、69 を中心として使用し、その近くの点の添字を見つけることができます。特定の位置に数字がある場合、それを1としてマークし、そうでない場合は0としてマークし、69を中心として、左に移動して最長の間隔を見つけ、合計が0になります。右に移動して見つけます。最長の間隔であり、合計は 0 です。ツリー配列を使用すると、間隔の合計、更新クエリの複雑さ、および数値の加算の複雑さを簡単に見つけることができます。

要件と目的:

• ツリー配列は間隔フラグの合計(特定の間隔の値が表示されるかどうか)を保存し、更新とクエリの複雑さはlognです

• 特定の値を中心にしてそれに最も近い値を見つけ、その添字、二分探索、複雑度 logn を返します

• スペースを時間と交換し、値 -> 添字マッピングを保存します。

• 配列の末尾に数字を追加できますが、順番に追加する必要はありません

次のコードは次の問題を解決します

配列 [5,9,3,8,7,10,12] があるとします

12 に最も近い座標を尋ねると、6 を返します
2 に最も近い座標を尋ねると、2 を返します
非繰り返しを追加します数値 15
反復しない数値 18 を追加します
反復しない数値 16 を追加します
反復しない数値 13 を追加します
13 に最も近い座標を求めると、10 を返します
17 に最も近い座標を求めると、9 を返します

リーリー

追加および削除操作を伴う動的クエリ (大きな数)

添え字が占める追加の間隔値を維持し、バランスのとれたバイナリ ツリーを設定し、複雑さのログをクエリし、複雑さのログを追加および削除する必要があります。