7

I have a NSMutableArray oldArray. Now, at one point, this NSMutableArray object gets updated with another NSMutableArray, which may have more, less or same number of elements as the previous NSMutableArray.

I want to compare the old and the new array for changes. What I want are two NSArrays addedArray and removedArray which will contain the indices of the elements which have been added and/or removed from the old array.

This whole problem will be more clear with an example : 

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

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

So, here the removed objects are @"b" and @"g" at indices 1 and 4 respectively. And the objects added are @"c", @"f" and @"h" at indices 1, 4 and 5 (first objects are removed, then added).

Therefore,

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

I want an efficient way to get these two arrays - removedArray and addedArray from the old and new NSMutableArray. Thanks! If the problem is not very understandable, I'm willing to provide more information.

Edit 1

Perhaps it will be more clear if I explain what I want to use this for.

Actually what I am using this for is updating a UITableView with methods insertRowsAtIndexPaths and removeRowsAtIndexPaths with animation after the tableview gets loaded, so that the user can see the removed rows go out and the new rows come in. The tableview stores the Favourites elements which the user can add or remove. So after adding some favorites and removing some; when the user comes back to the favourites tableview, the animations will be shown.

Edit 2

Should have mentioned this earlier, but the elements in both the old and the new array will be in an ascending order. Only the indices of the removal or addition matters. The order cannot be changed. ex. {@"b",@"a",@"c",@"d"} cannot be an array.

4

3 回答 3

5

我曾尝试使用循环和 if 条件遍历旧数组和新数组，但它是否变得非常混乱和错误。

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

a b c d
b c d e

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

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

这里有几个例子（我用括号括了 LCS 的元素）：

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

old不在LCS中的项目是1和4；不在LCS中的项目new是1、4和5。

这是另一个例子：

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

现在added是3和removed是0。

于 2013-06-26T10:03:52.520 回答
3

  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. 移除数组 = 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

于 2013-06-26T09:40:19.210 回答
1

如果两个数组都已按升序排序，则可以在两个数组上使用单个循环找到添加和删除的元素（使用两个独立的指向数组的指针）：

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);

输出：

删除：（
    1、
    4
)
添加： （
    1、
    4、
    5
)
于 2013-06-26T11:16:39.313 回答