如何更有效地从向量或集合中删除元素？

Question

如何更有效地从向量或集合中删除元素？

c++algorithmvectorset

3

问题陈述：

输入：

前两个输入是整数 n 和 m。n 是参加锦标赛的骑士数量 (2 <= n <= 100000，1 <= m <= n-1)。m 是将要进行的战斗数。

下一行包含 n 个力量值。

接下来的 m 行包含两个整数 l 和 r，表示第 i 场战斗中竞争的骑士位置范围。

每场战斗后，除了最高力量值的那个骑士外，所有骑士都将被淘汰。

每场战斗的范围是根据骑士的新位置而给出的，而不是原始位置。

输出：

输出 m 行，第 i 行包含那场战斗中骑士的原始位置（索引）。每行按升序排列。

示例输入：

8 4
1 0 5 6 2 3 7 4
1 3
2 4
1 3
0 1

示例输出：

这是该过程的可视化呈现。

          1     2
[(1,0),(0,1),(5,2),(6,3),(2,4),(3,5),(7,6),(4,7)]
       -----------------
                4     5
[(1,0),(6,3),(2,4),(3,5),(7,6),(4,7)]
             -----------------
          3           7
[(1,0),(6,3),(7,6),(4,7)]
       -----------------
    0
[(1,0),(7,6)]
 -----------

[(7,6)]

我已经解决了这个问题。我的程序产生了正确的输出，但是它的时间复杂度是O(n*m) = O(n^2)。我相信如果我更高效地从向量中删除骑士，效率可以提高。使用集合来删除元素会更有效吗？即删除连续的段而不是单个骑士。是否有其他更有效的方法来做到这一点？

#define INPUT1(x)  scanf("%d", &x)
#define INPUT2(x, y)  scanf("%d%d", &x, &y)
#define OUTPUT1(x) printf("%d\n", x);

int main(int argc, char const *argv[]) {
    int n, m;
    INPUT2(n, m);
    vector< pair<int,int> > knights(n);
    for (int i = 0; i < n; i++) {
        int power;
        INPUT(power);
        knights[i] = make_pair(power, i);
    }
    while(m--) {
        int l, r;
        INPUT2(l, r);
        int max_in_range = knights[l].first;
        for (int i = l+1; i <= r; i++) if (knights[i].first > max_in_range) {
            max_in_range = knights[i].first;
        }
        int offset = l;
        int range = r-l+1;
        while (range--) {
            if (knights[offset].first != max_in_range) {
                OUTPUT1(knights[offset].second));
                knights.erase(knights.begin()+offset);
            }
            else offset++;
        }
        printf("\n");
    }
}

- user6005857

2个回答

1

使用treap的解决方案非常简单。对于每个查询，您需要通过隐式键将treap拆分以获得对应于[l，r]范围的子树（它需要O(log n)时间）。然后，您可以遍历子树并找到力量最大的骑士。之后，您只需要将treap的[0，l）和[r + 1，end）部分与对应于此骑士的节点合并即可。显然，除了子树遍历和打印之外，解决方案的所有部分都在每个查询中以O(log n)的时间工作。但是，每个操作仅重新插入一个骑士并擦除范围内的其余部分，因此输出的大小（以及子树大小的总和）与n成线性关系。因此，总时间复杂度为O(n log n)。我认为您无法使用标准的stl容器来解决此问题，因为没有标准容器支持快速按索引获取迭代器和删除任意元素。

- kraskevich

我不明白如何从treap中获取与[l，r]范围对应的子树。此外，treap的每个节点都是一对吗？即（功率，初始位置）？ - user6005857

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- seleciii44 · Accepted Answer

好的，从向量中删除肯定不是高效的。从集合或无序集合中删除会更有效（使用迭代器而不是索引）。

但问题仍然是O(n^2)，因为你有两个嵌套的while循环运行n*m次。

--编辑--

我相信我现在理解了问题 :) 首先让我们计算一下你上面代码的复杂度。最坏的情况是所有战斗的最大范围都是1（每场战斗两个晚上），而且战斗没有按位置排序。这意味着你有m场战斗（在这种情况下m = n-1 ~= O(n)）

第一个while循环运行n次
For循环每次运行一次，总共是n*1=n
第二个while循环再次运行n次。
- 从向量中删除意味着n-1次移位，使其成为O(n)。

因此，使用向量的复杂性总复杂性为O(n^2)

首先，你实际上不需要内部for循环。将第一个骑士作为范围的最大值，逐一比较范围内的其余骑士并删除被打败的骑士。

现在，我相信可以使用std::map以O(nlogn)完成。映射的关键是位置，值是骑士的等级。

在继续之前，请注意，在映射中查找和删除元素是对数级别的，而迭代是常量级别的。

最后，你的代码应该如下所示：

while(m--) // n times
    strongest = map.find(first_position); // find is log(n) --> n*log(n)

    for (opponent = next of strongest; // this will run 1 times, since every range is 1
         opponent in range;
         opponent = next opponent) // iterating is constant
       // removing from map is log(n) --> n * 1 * log(n)
       if strongest < opponent
           remove strongest, opponent is the new strongest
       else
           remove opponent, (be careful to remove it after iterating to next)

好的，现在的上限将是 O(2*nlogn) = O(nlogn)。如果范围增加，这会使得上面循环的运行时间减少，但删除操作的数量增加。我相信上限不会改变，让我们把它作为一个作业留给你来计算 :)