C++ 计算在插入顺序之前删除的数组元素的计数

在这个问题中，我们将计算在将其插入数组之前从数组中删除的元素数量。

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

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

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

示例

输入

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 − 使用0初始化’cnt’以存储元素的数量。

步骤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’的值。

步骤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)。

空间复杂度 – 使用映射的空间复杂度为O(N)。

第二种方法比第一种方法的性能更好，但它需要更多的内存。然而，程序员可以使用队列数据结构来解决这个问题。