-2

ソートされていない配列があります。範囲 (2 つの配列インデックスとして表される) を指定し、その範囲 (つまり、配列の指定されたスライス) からの最大値を返す必要がある多数のクエリがあります。例えば：

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

任意の範囲から最大値をすばやく取得するには、どのアルゴリズムまたはデータ構造を構築すればよいでしょうか。（問い合わせが多い）

編集: 私はC++を使用しています

4

3 に答える 3

3

ある程度の前処理は許されると思います。Range Minimum Query問題（ここでは最大）です。 TopCoder でのこの問題の良いレビュー。適切なデータ構造: セグメント ツリーと平方根分解:

#include <cstdio>
#include <iostream>
#include <algorithm>

#define N int(3e4)

using namespace std;

int act[N], len, sz, res[N];

int answer(int l, int r) {
        int ret = -1, i;
        for (i = l; i % sz && i <= r; i++)
                ret = max(ret, act[i]);
        for (; i + sz <= r + 1; i += sz)
                ret = max(ret, res[i / sz]);
        for (; i <= r; i++)
                ret = max(ret, act[i]);
        return ret;                                            
}

int main() {
        int i, m;
        cin >> m;
        for (i = 0; ; i++) {
                cin >> act[i];
                if (act[i] == -1)
                        break;
        }
        len = i;

        for (sz = 1; sz * sz < len; sz++);

        for (int j = i + 1; j < sz * sz; j++)
                act[j] = -1;

        for (int i = 0; i < sz * sz; i++)
                res[i / sz] = max(res[i / sz], act[i]);

        for (int i = 0; i + m <= len; i++)
                cout << answer(i, i + m - 1) << endl;          

        return 0;
}
于 2013-05-04T10:26:18.063 に答える
0

これがあなたの配列だとしましょうarray[]={23,17,9,45,78,2,4,6,90,1};

配列がそれほど大きくない場合は、配列を前処理して、そのような別の配列を取得することをお勧めします。

{0,0} = 23; //between arr[0] and arr[0]
{0,1} = 23;
{0,2} = 23;
{0,3} = 45;

{9,9} = 1;

したがって、新しい配列は次のようになりますnewArr = {23,23,23,45,....., 1}

O(1) で検索を見つけることができます。たとえば、4 ～ 5 の間の最大値はnewArr[4*array.length+5)-1]; 合計で、n クエリの場合は O(n) になります。

スペースは、10000(10^4) integerがある場合、newArr = 10^8 * 4B = 400MBであるため、 int が 10000を超える場合、これは機能しません

EDIT：私は何かを考えましたが、MBoが言及しているTopcoderのアルゴリズムと同じです。

于 2013-05-04T10:43:54.850 に答える