c++ - 如何更有效地从 vector 或集合中删除元素？

Question

问题陈述:

输入:

前两个输入是整数 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
4 5
3 7
0

这是这个过程的可视化。

          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)。我相信，如果我更有效地从 vector 中删除骑士，则可以提高效率。使用集合删除元素会更有效吗？ IE。删除连续的段而不是单个骑士。有没有更有效的替代方法？

#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");
    }
}

Answer 1

嗯，从 vector 中删除肯定不会有效。从集合或无序集合中移除会更有效(使用迭代器而不是索引)。

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

--编辑--

我相信我现在明白了这个问题:)首先让我们计算上面代码的复杂性。最坏的情况是所有战斗中的最大射程为 1(每场战斗两晚)并且战斗没有根据位置排序。这意味着你有 m 场战斗(在这种情况下 m = n-1 ~= O(n))

• 第一个 while 循环运行 n 次
• For 每次运行一次，总共 n*1 = n
• 第二个 while 循环每次运行一次，这使得它再次 n 。
  • 从 vector 中删除意味着 n-1 次移动使其成为 O(n)。

因此，随着 vector 的复杂度，总复杂度为 O(n^2)

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

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

在继续之前，在map中查找和删除一个元素是对数的，迭代是常数。

最后，您的代码应如下所示:

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)。如果范围增加，这会使上层循环的运行时间减少但会增加删除操作的次数。我确定上限不会改变，让我们把它作为你计算的作业:)