查找NSArray/NSMutableArray更改的索引

Question

我有一个NSMutableArrayoldArray。现在，有一次，这个NSMutableArray对象被另一个NSMutableArray更新，其可能具有与先前的NSMutableArray更多，更少或相同数量的元素。

我想比较旧阵列和新阵列的变化。我想要的是两个NSArray s addedArray和removedArray它将包含已添加和/或从旧数组中删除元素的索引。

这整个问题会更加明了用一个例子：

oldArray = {@"a",@"b",@"d",@"e",@"g"}; 

newArray = {@"a",@"c",@"d",@"e",@"f",@"h"}; 

所以，在这里去除的各目标分别为@“b”和@“G”在索引1和4。并且在索引1,4和5处添加的对象是@“c”，@“f”和@“h”（第一个对象被删除，然后添加）。

因此，

removedArray = {1,4}; and addedArray = {1,4,5}; 

我希望有一个有效的方式来获得这两个数组 - 从新NSMutableArray老removedArray和addedArray。谢谢！如果问题不能理解，我愿意提供更多信息。

编辑1

也许如果我解释我想用这个东西它会更加明朗。

实际上我使用的是在tableview加载后用方法insertRowsAtIndexPaths和removeRowsAtIndexPaths更新UITableView，以便用户可以看到被删除的行出去并且新的行进入。tableview存储用户可以添加或删除的收藏夹元素。所以在添加一些收藏夹并删除一些后，当用户回到收藏夹桌面时，会显示动画。

编辑2

应该提到这较早，但在这两个旧的和新的数组中的元素将在升序排列。只有删除或添加事项的指标。订单不能更改。恩。 {@“b”，@“a”，@“c”，@“d”}不能是数组。

Answer 1

我已经尝试迭代旧的和新的数组使用循环，如果条件，但它变得非常混乱和越野车。

这不是一个简单的问题。首先，请注意，它可能有多种解决方案：

a b c d 
b c d e 

两个(a={0, 1, 2, 3}, r={0, 1, 2, 3})和(a={3}, r={0})是有效的解决方案。您可能要寻找的是最小的解决方案。

获得最小解决方案的一种方法是找到两个序列的Longest Common Subsequence (LCS)。用于查找LCS的算法将告诉您两个序列的哪些元素属于LCS，哪些不属于LCS。原始数组中不在LCS中的每个元素的索引都进入removed数组;新阵列中不在LCS中的元素索引将进入added阵列。

以下是几个例子（I括号LCS的元素）：

0 1 2 3 4 5 
(a) b (d) (e) g 
(a) c (d) (e) f h 

不LCS的的old项1和4;的new不是在LCS的项是1，4，和5

下面是另一个例子：

0 1 2 3 
a (b) (c) (d) 
(b) (c) (d) e 

现在added是3和removed是0。

Answer 2

1. addedArray = newArray∖（newArray∩oldArray）

    = newArray ∖ ({@"a",@"c",@"d",@"e",@"f",@"h"} ∩ {@"a",@"b",@"d",@"e",@"g"}) 
        = newArray ∖ {@"a",@"d",@"e"}    
        = {@"a",@"c",@"d",@"e",@"f",@"h"} ∖ {@"a",@"d",@"e"} 
        = {@"c",@"f",@"h"}    
   

2. removedArray = oldArray∖（oldArray∩newArray）

     = oldArray ∖ ({@"a",@"b",@"d",@"e",@"g"} ∩ {@"a",@"c",@"d",@"e",@"f",@"h"}) 
        = oldArray ∖ {@"a",@"d",@"e"} 
        = {@"a",@"b",@"d",@"e",@"g"} ∖ {@"a",@"d",@"e"} 
        = {@"b",@"g"} 
   

要查找阵列的交叉点，则可以查看以下SO帖子： Finding Intersection of NSMutableArrays

Answer 3

如果两个阵列以升序已经排序，可以找到的添加和删除 元件与单回路两个阵列上（使用两个独立的指针到阵列）：

NSArray *oldArray = @[@"a",@"b",@"d",@"e",@"g"]; 
NSArray *newArray = @[@"a",@"c",@"d",@"e",@"f",@"h"]; 

NSMutableArray *removedArray = [NSMutableArray array]; 
NSMutableArray *addedArray = [NSMutableArray array]; 

NSUInteger iold = 0; // index into oldArray 
NSUInteger inew = 0; // index into newArray 

while (iold < [oldArray count] && inew < [newArray count]) { 
    // Compare "current" element of old and new array: 
    NSComparisonResult c = [oldArray[iold] compare:newArray[inew]]; 
    if (c == NSOrderedAscending) { 
     // oldArray[iold] has been removed 
     [removedArray addObject:@(iold)]; 
     iold++; 
    } else if (c == NSOrderedDescending) { 
     // newArray[inew] has been added 
     [addedArray addObject:@(inew)]; 
     inew++; 
    } else { 
     // oldArray[iold] == newArray[inew] 
     iold++, inew++; 
    } 
} 
// Process remaining elements of old array: 
while (iold < [oldArray count]) { 
    [removedArray addObject:@(iold)]; 
    iold++; 
} 
// Process remaining elements of new array: 
while (inew < [newArray count]) { 
    [addedArray addObject:@(inew)]; 
    inew++; 
} 

NSLog(@"removed: %@", removedArray); 
NSLog(@"added: %@", addedArray); 

输出：

 
removed: (
    1, 
    4 
) 
added: (
    1, 
    4, 
    5 
)