1

インデックスiおよび整数kと共に Numbers のリストが与えられた場合、インデックスiの数字から (左に向かって) 最も遠く、 kより小さい数字のインデックスを見つけたいと思います。

eg
if the array is
Index :0 1 2 3 4 5 6 7 .....
Array :3 4 1 5 5 4 3 7 .....
Assuming i = 7 and k = 4 , the answer would be 0

Red Black Trees を使用してこれを実装しようとしましたが、 O(n) よりも低くすることはできませんでした。別のデータ構造を使用して複雑さを O(logn) に減らす方法はありますか?

4

2 に答える 2

2

実際、配列が静的であり、O(log n)それぞれに対して複数のクエリを実行する場合は、そのような複雑なデータ構造は必要ありません。

あなたが実際に求めているのは、「インデックスiの数値から最も遠く（左に向かって）、k未満の数値」です。i-「その前の左端の数がより小さい」に変換できますk。次に、これを次のように見ることができます。

  • K未満の左端の数を見つけます-位置にあると言いjます;
  • の場合j < i、j質問への回答です
  • それ以外の場合、そのような数はありません-位置の前のすべてのエントリは。i以上kです。

これらの質問の最初に答えるために知っておく必要があるのは、次のとおりです。位置iの場合、位置の最小数は何ですか。0..iこれをと呼びましょうmin(i)。は-minの単調減少関数であることに注意してください。の場合、は、への位置の最小数であり、これには必然的に、への位置の最小数が含まれます。これは、10であることがわかっています。構築-配列を呼び出すと、：、およびfor 。）imin(5) = 10min(6) = 15min(6)0605minamin(0) = a[0]min(i) = minimum(min(i - 1), a[i])i > 0

iこの情報を使用して、次のような左端のインデックスの二分探索を実行できますmin(i) < k。次に、の構築により、からまでの位置のすべての数値が。以上でminあることがわかります。だから、質問の答えでなければなりません。0i - 1ki

于 2012-10-10T22:38:28.507 に答える
1

mp1 つの方法は、0 <= j < n ごとに、最初の j 要素の最小値のインデックスを含む配列を構築することです。

int minPos = 0;
for (int i = 0; i < n; ++i) {
    if (a[i] < a[minPos]) minPos = i;
    mp[i] = minPos;
}

これには明らかに O(n) 時間がかかります。

の要素は、減少する値を持つmp入力配列の要素を参照します。aクエリ (i, k) を指定するmpと、範囲 [0, i - 1] で k のバイナリ検索ができるようになりました。間接参照を使用して、最小インデックスから実際の最小値を取得します。

int find(int i, int k) {
    int start = 0;
    int end = i - 1;

    if (a[mp[end]] >= k) return -1;    // Not found.
    if (a[mp[start]] < k) return mp[start];    // The first element is smaller.

    // We maintain the invariant that a[mp[start]] is >= k and a[mp[end]] is < k.
    while (end - start > 1) {
        int mid = (start + end) / 2;
        if (a[mp[mid]] < k) {
            end = mid;
        } else {
            start = mid;
        }
    }

    return mp[end];
}
于 2012-10-10T22:43:24.180 に答える