3

並べ替えられていない大きな配列が与えられた場合、特定の範囲内で特定の数値が出現する回数を調べる必要があります。（問い合わせが多いかもしれません）

たとえば、 arr[]={ 6,7,8,3,4,1,2,4,6,7,8,9}とleft_range=3andright_range=7とnumber=4の場合、出力は 2 になります (0 インデックス配列を考慮)。

arr[i] の範囲は 1 ～ 100000 です。配列には最大 100000 個の数値を含めることができます。

ここで使用するデータ構造またはアルゴリズムについて教えてもらえますか?

PS: 配列の前処理は許可されています。

4

1 に答える 1

11

これは、セグメント ツリーを必要としないソリューションです。

前処理:

  1. number ごとarr[i]に、 i を index で 2D ベクトル (または ArrayList) にプッシュしますarr[i]。

質問への回答:

任意のクエリに対して、vector[num] でバイナリ検索を実行して、正しい範囲以下のそのベクトル内の num の最大インデックスのインデックスを見つけます。これを R と呼びましょう。次に、以上の最小インデックスを見つけます。左の範囲、それを L としましょう R - L + 1 を出力してください

ランタイム: アイテムごとに O(1) で前処理し、合計 O(N) 時間かかります。クエリごとの回答: O(lg(N))

スペース: vector または ArrayList を想定してかなり線形

于 2014-03-16T05:22:34.443 に答える