删除和移位数组元素

假设我有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

删除和移位数组元素

回答

相关问题