NSArray和最长公共子序列

这是一个带有找到与另一个数组共有最长子序列索引的类别的NSArray。

UITableView有内置的添加和删除带有动画的cells的方法，但它没有一种方式可以窥视您的数据源以了解其变化。了解列表中哪些元素被移除、哪些保持不变以及哪些被添加，这似乎是计算机特别擅长的事情。实际上确实如此。

这种技术称为《最长公共子序列》。我为《NSArray》编写了一个类别来计算这个。针对实际的算法，我使用了自下而上的动态规划解决方案，结果存储在C矩阵中。它并不复杂，并且我毫无耻辱地窃取了我的实现，来源于这个页面。您还可以在维基百科上找到更详细的解释。

该算法以O(mn)的时间复杂度运行，其中m和n是两个数组的长度。对象的比较通过isEquals:方法进行，因此请确保您实现的isEquals:确实代表您对象的相等性。

生成共有子序列长度的表是第一步。一旦我们有子序列长度的表，我们可以通过它回溯以获取共有对象的索引。这种技术在几个地方也有记录，包括上面提到的两个链接。然后我们使用commonIndexes来找到 addedIndexes 和 removedIndexes。

用法

如果您只需要共同的索引，有一个方便的方法供您使用

- (NSIndexSet*) indexesOfCommonElementsWithArray:(NSArray*)array;

一旦您有了NSIndexSet，您可以通过调用-[NSArray objectsAtIndexes:]来轻松访问对象本身。

当然，这是Cocoa，我们想能在UIKit（即UITableView和UICollectionView）中使用这些信息。为了获取用于-insertRowsAtIndexPaths:withRowAnimation:和-deleteRowsAtIndexPaths:withRowAnimation:方法的索引，请使用第二个提供的方法。它有两个inout参数，这些参数会返回所需额外数据的地址。

- (NSIndexSet*) indexesOfCommonElementsWithArray:(NSArray*)array addedIndexes:(NSIndexSet**)addedIndexes removedIndexes:(NSIndexSet**)removedIndexes;

一般情况下实现

您可以看到，对于任何一般的数据集，一个示例实现相当简单。

NSIndexSet *addedIndexes, *removedIndexes;

[oldData indexesOfCommonElementsWithArray:newData addedIndexes:&addedIndexes removedIndexes:&removedIndexes];

self.dataSource = newData;

NSMutableArray *indexPathsToAdd = [NSMutableArray array], *indexPathsToDelete = [NSMutableArray array];

[addedIndexes enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
    [indexPathsToAdd addObject:[NSIndexPath indexPathForRow:idx inSection:0]];
}];
[removedIndexes enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
    [indexPathsToDelete addObject:[NSIndexPath indexPathForRow:idx inSection:0]];
}];

[_tableView beginUpdates];
[_tableView insertRowsAtIndexPaths:indexPathsToAdd withRowAnimation:UITableViewRowAnimationAutomatic];
[_tableView deleteRowsAtIndexPaths:indexPathsToDelete withRowAnimation:UITableViewRowAnimationAutomatic];
[_tableView endUpdates];

关于addedIndexes的说明

找到正确的索引以添加的关键（一如既往地）在Apple文档中。

[])