複製並取消int數組

Question

我得到了兩個數組，都進行了排序。一個數組填充重複值，另一個填充值應在第一個數組中取消。例如：

int * val = new int[11]; 
val[0] = 1; val[1] = 1; 
val[2] = 2; val[3] = 2; val[4] = 2; val[5] = 2; 
val[6] = 3; 
val[7] = 4; 
val[8] = 5; val[9] = 5; val[10] = 5; 

int * invalid = new int[2]; invalid[0] = 2; invalid[1] = 5; 

然後輸出應是這樣的

int * valid = new int[4]; 
valid[0] = 1; valid[1] = 1; 
valid[2] = 3; 
valid[3] = 4; 

我如何能實現這有效地使用for循環？我想指出，我不想切換到像vector或list這樣的容器，因爲我知道會有朝這個方向發展的評論。我明確想要使用數組。

Answer 1

首先，您應該計算源數組中滿足條件的元素數量，然後爲元素分配足夠的內存。

這裏是一個示範項目

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    const size_t N1 = 11; 
    const size_t N2 = 2; 
    int * val = new int[N1] { 1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 5 }; 
    int * invalid = new int[N2] { 2, 5 }; 
    int *valid = nullptr; 

    auto n = std::count_if(val, val + N1, 
          [=](int x) { return !std::binary_search(invalid, invalid + N2, x); }); 

    if (n) 
    { 
     valid = new int[n]; 

     std::copy_if(val, val + N1, valid, 
         [=](int x) { return !std::binary_search(invalid, invalid + N2, x); }); 
    } 

    if (valid) std::copy(valid, valid + n, std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 

    return 0; 
} 

它的輸出是

1 1 3 4 

您可以使用標準算法std::binary search如果無效的數組有很多元素，或者你可以只寫lambda表達式像

[=](int x) { return x != invalid[0] && x != invalid[1]; } 

例如

#include <iostream> 
#include <algorithm> 
#include <iterator> 

int main() 
{ 
    const size_t N1 = 11; 
    const size_t N2 = 2; 
    int * val = new int[N1] { 1, 1, 2, 2, 2, 2, 3, 4, 5, 5, 5 }; 
    int * invalid = new int[N2] { 2, 5 }; 
    int *valid = nullptr; 

    auto is_valid_element = [=](int x) { return x != invalid[0] && x != invalid[1]; }; 
    auto n = std::count_if(val, val + N1, is_valid_element); 

    if (n) 
    { 
     valid = new int[n]; 

     std::copy_if(val, val + N1, valid, is_valid_element); 
    } 

    if (valid) std::copy(valid, valid + n, std::ostream_iterator<int>(std::cout, " ")); 
    std::cout << std::endl; 

    return 0; 
} 

編譯器應支持C++ 2011

Answer 2

概念，像這樣的僞代碼的算法：

int i, j; 

j = 0; 
for (i=0; i < length(val); i++) { 
    if (val[i] != VALUE_TO_DELETE) { 
    val[j++] = val[i]; 
    } 
} 
... now discard, or ignore, anything in "val" beyond element #j. 

我們只是通過遍歷數組，複製任何東西，是不是我們想甩掉的價值。 i是用於查找值的光標，並且j表示在何處放置它們。

超出元素的值＃j仍然存在，物理上，但您忽略它們。

---

爲了完整起見，如果我們正在尋找invalid號：

int i, j, k; 
boolean delete_me; 

j = 0; 
for (i=0; i < length(val); i++) { 

    // search the "invalid" list to see if the number is in it 
    delete_me = false; 
    for (k = 0; k < length(invalid); k++) { 
    if (val[i] == invalid[k]) { 
     delete_me = true; 
     break;    // quit the loop as soon as we know ... 
    } 
    } 

    // copy what is NOT in it 
    if (!delete_me) {  // notice: "if NOT" ... 
    val[j++] = val[i]; 
    } 
} 

Answer 3

如果同時進行排序，這只是一個簡單的O（N + M）算法：先從兩個數組在零索引處，並增加指向較小值的那一個。如果您增加了目標數組，請複製，除非它等於無效數組。

此外，由於您只是刪除項目，所以如果您不必保留原始數據，則可以避免一些副本：您可以保留一個計數器丟棄多少項目，並將其複製到currentIdx-discardedCount if discardedCount大於零。

Answer 4

#include <iostream> 
const int SIZE_1 = 11; 
const int SIZE_2 = 2; 

/*find out if item should be exclude from result array; this take linear time over the size of the invalids array*/ 

bool doNotInclude(int item, int invalids[], int size) 
{ 
    bool remove = false; 
    for(int i = 0; i < size; i++) 
    { 
     if(invalids[i] == item) 
     { 
      remove = true; 
     } 
    } 
    return remove; 
} 

int main() { 

    //array of values 
    int * val = new int[SIZE_1] { 1, 5, 2, 2, 2, 2, 3, 4, 1, 5, 5 }; 

    //values to ignore 
    int * invalid = new int[SIZE_2] { 2, 5 }; 

    //result array 
    int *valid = new int[SIZE_1]; 

    //keep track of result array current index/ size 
    int currentIndex = 0; 

    /*check if elements of input array are in invalids, if not put them in the result array*/ 

    for(int i = 0; i < SIZE_1; i++) 
    { 
     if(!doNotInclude(val[i], invalid, SIZE_2)) 
     { 
      valid[currentIndex] = val[i]; 
      currentIndex++; 
     } 
    } 

    //print result 
    //currentIndex is now the size of the valid array 
    for(int n = 0; n < currentIndex; n++) 
    { 
     std::cout << valid[n] << ' '; 
    } 

} 

做的這種方法是O（N * M）的陣列是否被排序或沒有。