查找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 
)