时间戳

首页 > 解决方案 > 一个数字在所有查询中出现的次数？

c++ - 一个数字在所有查询中出现的次数？

问题描述

取一个未排序的数组，如：

4,5,1,2,3,7,8,3

查询如下：

[1 2] [5 5] [2 6] [6 6] [1 6] [1 5]

其中每个查询代表一个索引区间。

数组和总查询的长度可以达到100000。

我想计算每个查询中每个索引的出现次数，如下所示：

发生率 1: 3

发生 3: 3

5：4等的出现

执行此操作的任何最佳方法？我以天真的方式尝试过，但需要一些提示以获得最佳解决方案。

标签： c++arraysalgorithmdata-structuresstl

解决方案

您可以通过BIT（二叉索引树）或Segment-Tree来解决它。

我在那里附上了两个链接来了解这些算法......

比特解决方案：

对于每个查询，让范围[l r]：：

  • 现在您需要在 BITl to n中使用 value进行更新1。
  • 现在你需要排除更新r+1 to n......所以用BITr+1 to n中的值更新......-1

每个更新操作都在 BIT 中记录 log(n)...

计算每个索引的出现次数：

Call sum(index) in BIT to get count

此操作需要 log(n) 时间..

复杂：

该解决方案的复杂性：Q*(log(n)+log(n)) + N *(log(n))..

代码：

#include <bits/stdc++.h>
using namespace std;
int tree[100005], A[100005];

void update(int idx, int n, int v) {
    while (idx <= n) {
        tree[idx] += v;
        idx += (idx & -idx);
    }
}

int sum(int idx) {
    int res = 0;
    while (idx) {
        res += tree[idx];
        idx -= (idx & -idx);
    }
    return res;
}

int main() {
    int n, q, i, l, r;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
    }
    scanf("%d", &q);
    memset(tree, 0, sizeof(tree));
    while (q--) {
        scanf("%d%d", &l, &r);
        update(l,n,1);
        update(r+1,n,-1);
    }
    for (i = 1; i <= n; i++) {
        printf("%d\n", sum(i));
    }
    return 0;
}

推荐阅读