刪除和移位數組元素

假設我有2個排序數組。其中一個有從另一個刪除的元素。例如刪除和移位數組元素

int array1[]={1,2,3,4,5,6,7,8,9,10,11,12,13}; 
    int delete[]={5,9,12};

我應該如何刪除從ARRAY1刪除數組中指示的元素，其餘的ARRAY1有效地轉移？

我不想查看array1的所有元素，因爲其中一些元素將保持不變。所以我想從

int j,i=0,n=0; 
    for(j=delete[i+n];j<delete[i+1+n];j++){ 
     array1[i-n]=array1[i+1-n]; 
     n++; 
    }

但我無法弄清楚如何做到這一點。有任何想法嗎？

來源

2013-12-22 Ege

任何特定語言？如果不是，請標記爲'language-agnostic'。 –

是否有任何限制？像數組中的值範圍一樣？你可以爲array1使用不同的數據結構嗎？ –

您沒有指定語言。我會結合這些數組，使它們成爲一組並對結果重新排序。

set combined_set = new Set(array1 + array2) 
array = new Array(combined_set).sort()

來源

2013-12-22 16:10:01 Max

但是這些元素不會被這種方式刪除，對吧？ – remus

重複的元素將被刪除。 – Max

從數組中刪除任何元素是O（N）操作。您可以執行以下操作。

初始化I = 0計數= 0
迭代通過ARRAY1 []和搜索元件刪除[i]中。
如果遇到元素array1 [j]> delete [i]，這意味着delete [i]在array []中不存在。增加i以檢查刪除數組中的下一個元素。
如果你找到一個元素array1 [j] == delete [i]，然後增加count。並增加i。
繼續將array1 [j]複製到array1 [j - count]。

array1 [j - count] = array1 [j];
繼續直到array1結束。最後，將array1的大小調整爲大小size - count。

來源

2013-12-22 16:18:39

這可以在array1[]和delete[]的兩步掃描中完成。

同時掃描這兩個數組，並記得在array1[]其值也出現在delete[]的位置。
根據您在第一步中獲得的職位，您應該知道，對於array1[]中的每個值，從delete[]中刪除值後應該是什麼職位。然後只需複製到正確的位置。完成！

所有方法可以在爲O（n）來完成。

來源

2013-12-22 16:33:09 herohuyongtao

假設的聲明是這樣的：

var 
    TgtArr : array of integer; // given- sorted array of elements to be modified 
    TgtArrLen : integer;  // given- count of elements in TgtArr 
    DelArr : array of integer; // given- sorted list of elements to be deleted 
    DelArrLen : integer;  // given- count of elements in DelArr

，並宣佈這些工作變量：

var PutPtr, GetPtr, DelPtr : integer; // local to deletion operation

這個片段將完成刪除：

DelPtr := 0; 
    PutPtr := 0; 
    for GetPtr := 0 to TgtArrLen-1 do begin 
     if TgtArr[GetPtr]<>DelArr[DelPtr] then begin 
     TgtArr[PutPtr] := TgtArr[GetPtr]; 
     PutPtr := PutPtr+1; 
     end; 
     if TgtArr[GetPtr]>=DelArr[DelPtr] then begin 
     DelPtr := DelPtr+1; 
     if DelPtr>=DelArrLen then break; // out of "for GetPtr" loop 
     end; 
    end; 
    TgtArrLen := PutPtr;

（這是德爾福帕斯卡，但你得到想法）。

來源

2013-12-22 16:56:20

如果你不想改變數據結構，我們可以簡單地用兩個

二進制搜索

搜索元素的下界和上限你想要刪除。例如數組{1,1,2,2,3,3,3,4,5}和刪除元素是3，所以我們有起始索引和結束索引是4和6.

下一步是這麼簡單，只需摺疊上述兩個索引指定的段即可。

如果您想擁有更快的性能，我建議你可以使用二叉搜索樹，或存儲元件的頻率的數組。

來源

2013-12-23 04:10:16

刪除和移位數組元素

回答

相關問題