1

問題は次のとおりです。サイズNの配列が与えられます。q =クエリの数も与えられます。クエリでは、l = 下限範囲、u = 上限範囲、およびnum = l~u に頻度をカウントする必要がある数が与えられます。

次のように C++ でコードを実装しました。

#include <iostream>
#include <map>

using namespace std;

map<int,int>m;

void mapnumbers(int arr[], int l, int u)
{
    for(int i=l; i<u; i++)
    {
        int num=arr[i];
        m[num]++;
    }
}


int main()
{
    int n; //Size of array
    cin>>n;

    int arr[n];

    for(int i=0; i<n; i++)
        cin>>arr[i];

    int q; //Number of queries
    cin>>q;

    while(q--)
    {
        int l,u,num;   //l=lower range, u=upper range, num=the number of which we will count frequency
        cin>>l>>u>>num;
        mapnumbers(arr,l,u);
        cout<<m[num]<<endl;
    }

    return 0;
}

しかし、私のコードには問題があり、各クエリでマップが空になりません。そのため、同じ数を2回/3回クエリすると、以前に保存された頻度のカウントが追加されます。

これを解決するにはどうすればよいですか？10 ^ 5 のような広範囲のクエリに対しては貧弱なプログラムでしょうか? この問題の効率的な解決策は何ですか?

4

4 に答える 4

2

クエリの SQRT 分解を使用してタスクを解決できます。複雑さは O(m*sqrt(n)) になります。まず、次の基準に従ってすべてのクエリを並べ替えます。L/sqrt(N) は増加している必要があります。ここで、L はクエリの左境界です。等しい L/sqrt(N) の場合、R (右境界) も増加するはずです。N はクエリの数です。次に、これを行います。最初のクエリの答えを計算します。次に、このクエリの境界を次のクエリの境界に1 つずつ移動します。たとえば、並べ替え後の最初のクエリが [2,7] で 2 番目のクエリが [1, 10] の場合、左境界を 1 に移動し、[2] の頻度を減らし、1 の頻度を増やします。. 右境界を 7 から 10 に移動します。a[8]、a[9]、および a[10] の頻度を増やします。マップを使用して周波数を増減します。これは非常に複雑な手法ですが、タスクをかなり複雑に解決することができます。ここで、クエリの SQRT 分解について詳しく読むことができます: LINK

于 2015-05-05T16:01:42.643 に答える
0

マップをクリアするには、次を呼び出す必要がありますmap::clear()。

void mapnumbers(int arr[], int l, int u)
{
    m.clear()

問題をクリアするためのより良いアプローチは、ループまたは関数mに対してローカル変数を作成することです。while (q--)mapnumbers

ただし、一般的に、マップが必要な理由は非常に奇妙です。とにかく配列全体をトラバースし、カウントする必要がある数を知っているので、そうしないのはなぜですか

int mapnumbers(int arr[], int l, int u, int num)
{
    int result = 0;
    for(int i=l; i<u; i++)
    {
        if (arr[i] == num);
            result ++;
    }
    return result;
}

操作は O(log N) であるため、これはより高速で、漸近的にも高速になりmapます。したがって、元のソリューションはクエリごとに O(N log N) で実行されましたが、この単純な反復は O(N) で実行されます。

ただし、非常に大きな配列と多くのクエリの場合 (競合するプログラミング サイトで問題が発生しているのではないでしょうか?)、これでも十分ではありません。O(log N) クエリを可能にするデータ構造とアルゴリズムが必要だと思いますが、今は考えられません。

UPD:問題で配列が変更されないことに気付きました。これにより、クエリ ソリューションごとに単純な O(log N) が可能になり、はるかにシンプルになります。入力配列内のすべての数値を並べ替え、元の位置も記憶する必要があります (元の位置が昇順になるように、並べ替えが安定していることを確認します)。これは 1 回だけ実行できます。この後、すべてのクエリは 2 つのバイナリ検索だけで解決できます。

于 2015-05-05T15:56:13.467 に答える