找出NSArray/NSMutableArray更改的索引位置

Question

我有一个名为oldArray的NSMutableArray。现在，在某一点上，这个NSMutableArray对象将被另一个NSMutableArray更新，后者可能具有比前一个NSMutableArray更多、更少或相同数量的元素。

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

通过以下示例可以更清楚地了解整个问题：

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

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

在这里，被删除的对象是位于索引1和4的@"b"和@"g"。同时，在索引1、4和5添加了@"c"、@"f"和@"h"（先删除原有对象，再添加新的对象）。

因此，

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

我希望能够从旧的和新的NSMutableArray中高效地获取这两个数组-removedArray和addedArray。谢谢！如果问题不是很清楚，我可以提供更多信息。

编辑1

如果我解释一下我想用这个做什么，可能会更清楚。

实际上，我正在使用它来更新一个UITableView，使用方法insertRowsAtIndexPaths和removeRowsAtIndexPaths进行加载后的动画，以便用户可以看到删除的行出去，新的行进来。 TableView存储用户可以添加或删除的收藏夹元素。因此，在添加一些收藏夹并删除一些收藏夹后，当用户返回到收藏夹tableView时，将显示动画。

编辑2

应该早点提到，但是旧数组和新数组中的元素将按升序排列。只有删除或添加的索引才重要。顺序不能改变。例如，{@"b",@"a",@"c",@"d"}不能是一个数组。

- aksh1t

---

我尝试使用循环和if条件迭代旧和新数组，但是这变得非常混乱和有缺陷。它适用于某些情况，而对于其他情况则不行。我在想是否有一种使用NSMUtableArray的方法可以简化我想做的事情。 - aksh1t

你真的需要添加和删除对象的索引吗？对我来说，这更像是 NSSet 的工作。或者是 NSMutableSet。您可以统一集合，从另一个集合中删除一个集合，识别交集等等。而且，您可以从数组中创建它们，反之亦然。但是您将失去索引。 - Hermann Klecker

@HermannKlecker - 我只需要被移除和添加元素的索引。这些用于在表视图中使用insertRowsAtIndexPaths和removeRowsAtIndexPaths方法进行动画处理。 - aksh1t

在上面的例子中有两个数组。它们都有一个NSString元素，其内容为@"a"。这是两个相同类型和值的对象。由于您希望将它们应用于重新对齐表视图，那么在您具体的情况下，您的示例中表示@"a"的这两个对象实际上是完全相同的对象实例吗？如果它们是同一个对象，则可以使用NSArray内置方法轻松解决该问题。 - Hermann Klecker

可能最简单的方法是将它们放入NSSets中，在集合上执行“逻辑”操作，然后找到原始数组中的项以产生所需的索引。虽然可能不是最有效率的方法。 - Hot Licks

Answer 1

我尝试使用循环和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；new 中不在 LCS 中的项目是 1、4 和 5。

以下是另一个例子：

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

现在 added 是 3，而removed是0。

- Sergey Kalinichenko

---

哦，我真是太愚蠢了，但我应该在问题中提到，旧数组和新数组中的元素将始终按升序排列。b c d a 不可能出现。它只会按升序添加或删除元素。我会编辑问题。 - aksh1t

@aksh1t 没问题，LCS算法可以用于任意序列。 - Sergey Kalinichenko

@aksh1t，我进行了编辑以确保两个序列都是按升序排列的。 - Sergey Kalinichenko

哇，好的。这是我可以在循环和条件语句中处理的东西。谢谢！稍后会接受。 - aksh1t

@aksh1t 我链接的文章中有一个关于打印差异的部分，你可以通过存储索引而不是打印元素来调整该算法以满足你的需求。 - Sergey Kalinichenko

在这里找到了一个实现，但我还没有尝试过 - https://github.com/khanlou/NSArray-LongestCommonSubsequence - trss

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帖子：查找NSMutableArrays的交集

- Ozair Kafray

---

每个问题都有一种优美、简洁、快速但不正确的解决方案。这就是其中之一 :) 为了明显地看出它是不正确的，请考虑当新数组是已被旋转一个元素的旧数组时，该算法会产生什么结果：这个算法将产生两个空答案。 - Sergey Kalinichenko

这个，就像@dasblinkenlight所说的那样，并不能满足我的目的，因为我需要获取索引。实际上，我使用它来更新UITableView，使用insertRowsAtIndexPaths和removeRowsAtIndexPaths方法并且有动画效果，以便在tableview加载后，用户可以看到被删除的行消失了，新的行出现了。 - aksh1t

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

输出:

已删除: (
    1,
    4
)
已添加: (
    1,
    4,
    5
)

- Martin R

---

这正是我所做的（不过我用的是for循环而不是while）。感谢您的回答！我接受了另一个答案，因为它帮助我理解了解决方案。无论如何还是非常感谢。 - aksh1t