陣列元素中刪除順序先於插入順序的元素個數

---

在這個問題中，我們將計算從陣列中刪除的元素個數，這些元素在被插入到陣列之前就被刪除了。

解決這個問題的邏輯部分是檢查所有數字，看它在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)。

第二種方法比第一種方法具有更好的效能，但它佔用更多的記憶體。但是，程式設計師可以使用佇列資料結構來解決問題。