数组元素中删除顺序先于插入顺序的元素个数

---

在这个问题中，我们将计算从数组中删除的元素个数，这些元素在被插入到数组之前就被删除了。

解决这个问题的逻辑部分是检查所有数字，看它在remove[]数组中的位置是否在它在insert[]数组中的位置之前。如果是，我们可以将remove[]数组的该特定元素计入答案。

但是，我们将使用map数据结构来提高代码的性能。

问题陈述 - 我们给出了一个insert[]数组和一个remove[]数组，它们包含前N个整数。insert[]数组表示我们将元素插入数组的顺序，remove[]数组表示元素被删除的顺序。我们需要找到在插入之前被删除的元素的数量。

示例

输入

insert[] = {1, 2, 5, 3, 6, 4}, remove[] = {1, 3, 4, 5, 6, 2};

输出

2

解释 - 3和4在被插入到数组之前就被删除了。

输入

insert[] = {4, 3, 2, 1}, remove[] = {4, 3, 2, 1}

输出

0

解释 - 所有元素都在插入后被删除。

输入

insert[] = {1, 2, 3, 4, 5, 6}, remove[] = {2, 3, 4, 5, 6, 1};

输出

5

解释 - 除1之外，所有元素都在插入前被删除。

方法1

此方法将使用两个嵌套循环来遍历insert[]和remove[]数组。对于insert[]数组的每个元素，我们将检查它在remove[]数组中的位置，并计算remove[q] == insert[p]且q < p的个数。

算法

步骤1 - 将‘cnt’初始化为0，以存储元素的数量。

步骤2 - 使用for循环遍历insert[]数组。此外，使用另一个嵌套for循环遍历remove[]数组。

步骤3 - 如果insert[]数组中索引p处的元素与remove[]数组中索引q处的元素相同，且q小于p，则将‘cnt’值加1。

步骤4 - 否则，如果insert[p]和remove[q]相同，但q不大于p，则中断循环。

步骤5 - 打印‘cnt’值。

示例

#include <bits/stdc++.h>
using namespace std;

int findMaximumCnt(int insert[], int remove[], int n) {
    int cnt = 0;
    // Traverse insert[] and remove[] array and find position of each elements
    for (int p = 0; p < n; p++) {
        for (int q = 0; q < n; q++) {
            if (insert[p] == remove[q] && q < p) {
                cnt++;
            } else if (insert[p] == remove[q]) {
                break;
            }
        }
    }
    return cnt; // Return the total number of elements removed before insertion
}

int main() {
    int N = 6;
    int insert[] = {1, 2, 5, 3, 6, 4};
    int remove[] = {1, 3, 4, 5, 6, 2};
     cout << "The total number of elements removed before insertion is " << findMaximumCnt(insert, remove, N) << endl;
    return 0;
}

输出

The total number of elements removed before insertion is 2

方法2

在此方法中，我们将使用map数据结构。我们将insert[]数组的每个元素的位置存储到map中。之后，我们将遍历remove[]数组，并将它的每个元素的位置与insert[]数组的位置进行比较。

算法

步骤1 - 定义map来存储整数类型的键和值。

步骤2 - 将insert[]数组的所有元素插入到map中，并使用元素的索引值作为键。

步骤3 - 将‘cnt’初始化为0。

步骤4 - 遍历remove[]数组。

步骤5 - 如果索引p小于mp[remove[p]]，则将‘cnt’值加1。

步骤6 - 打印‘cnt’值。

示例

#include <bits/stdc++.h>
using namespace std;

int findMaximumCnt(int insert[], int remove[], int n) {
    // Map to store elements of insert[] array
    map<int, int> mp;
    // Insert elements into the map
    for (int p = 0; p < n; p++) {
        mp[insert[p]] = p;
    }
    int cnt = 0;
    // Count elements of remove[] array, whose index in the insert[] array is large
    for (int p = 0; p < n; p++) {
        if (p < mp[remove[p]]) {
            cnt++;
        }
    }
    return cnt;
}
int main() {
    int N = 6;
    int insert[] = {1, 2, 5, 3, 6, 4};
    int remove[] = {1, 3, 4, 5, 6, 2};
    cout << "The total number of elements removed before insertion is " << findMaximumCnt(insert, remove, N) << endl;
    return 0;
}

输出

The total number of elements removed before insertion is 2

时间复杂度 - 遍历数组需要O(N)。

空间复杂度 - 使用map需要O(N)。

第二种方法比第一种方法具有更好的性能，但它占用更多的内存。但是，程序员可以使用队列数据结构来解决问题。