“同步”2阵列的算法

Array 1 | Array 2 
================= 
    1 | 2 
    2 | 3 
    3 | 4 
    5 | 5 
     | 6

什么是“同步”或将数组2合并到数组1中的好算法？下面需要做的：“同步”2阵列的算法

整数数组中2，但不是在阵列1应加入阵列1
在整数数组都可以单独留下。
整数数组1，但不是在阵列2应从阵列中除去1

我最终会在的OBJ-C进行编码这一点，但我真的只是寻找一个伪代码表示一种有效的算法来解决这个问题，所以你可以随意以任何形式提出答案。

编辑：

最终的结果我需要的是有点硬不给背景故事来解释。我有一个Cocoa应用程序，它有一个Core Data实体，其数据需要用来自Web服务的数据进行更新。因为Array 1与我的应用程序中的其他核心数据实体有关系，所以我不能简单地用Array 2的内容（从Web解析到数组中的数据）覆盖Array 1（核心数据实体）的内容。所以基本上重要的是包含在两个数组中的整数在数组之一中不会被覆盖。

来源

2008-12-26 macinjosh

如果您在给出示例输入的情况下写出了预期的答案，您会发现@Yuliy会给出答案。否则，考虑集合论 - 设置联合，集合差异;之类的东西。这将适用于您的问题的其他变体。 – 2008-12-27 00:11:27

编辑后：然后有你还没有给我们的信息;也许你没有意识到这很重要？ 3-check算法不是你想要的，或者是其他重要的东西，比如数组中的位置。但是按照书面的说法，你需要Array1中的Array2副本。 – 2008-12-27 05:21:01

（续）：也许如果你告诉我们结果应该如何与Array2的副本不同，那么我们会更好地理解你的问题。 – 2008-12-27 05:21:38

我有点猜测，因为你的例子在空中留下了一些东西，但通常在这种情况下，我会使用一套。以下是Obj-C中的一些示例代码。

NSMutableSet *set = [NSMutableSet set]; 
[set addObjectsFromArray:array1]; 
[set addObjectsFromArray:array2]; 
NSArray *finalArray = [[set allObjects] sortedArrayUsingSelector:@selector(compare:)];

来源

2008-12-27 03:02:29

Array1 = Array2.Clone()或某些等价物可能是最简单的解决方案，除非元素的顺序很重要。

来源

2008-12-26 22:20:26 Yuliy

好吧，如果订单不打紧，你已经有你的算法：

整数数组中2，但不是在阵列1应在两个数组被添加到阵列1.
整数可以独自一人。
整数数组1，但不是在阵列2应阵列1.

被删除。如果事情的整数的顺序，你想要什么是决定两者之间的“差异化”的算法变化字符串。 Levenshtein算法应该适合你的情况。

但是，我怀疑你实际上是想要第一部分。那么，究竟是是什么问题？如何在数组中找到整数？或者是什么？

来源

2008-12-26 22:23:46

在我的方法中，您将需要Set data structure。我希望你能在Obj-C中找到一些实现。

将Array1的所有元素添加到Set1 ，并对Array2到Set2执行相同的操作。
循环遍历Array1的元素。检查它是否包含在Set2中（使用提供的方法）。如果它不是，则从Set1中删除该元素。
循环遍历Array2的元素。如果它尚未在Set1中存在，请将其添加到Set1。

Set1的所有元素现在是您的“同步”数据。

对于一些很好的实现（如HashSet）中的“包含”，“删除”和“添加”操作的“设置”算法复杂度会给你想要的效率。

编辑：这是一个简单的实施Set假定整数都在0范围有限 - 100初始化为0，每个元素，只给约套装更清晰的概念。

首先需要限定尺寸101的阵列桶然后为..

含有（n）的 - 检查是否桶[n]是1或不是。
附加（n）的 - 设定铲斗[n]至1
删除（n）的 - 设定铲斗[n]至0

来源

2008-12-26 22:34:56 Gant

（假设这不是一个简单的Array1 = Array2问题），如果数组已排序，那么您正在查看两个数组上的单个O（n + m）传递。指向两个数组的开始，然后前进包含较小元素的指针。继续比较元素，并相应地添加/删除元素。如果它们不是这样的，那么这样做的效率可能值得对数组进行排序。

来源

2008-12-26 22:37:39 aib

你说：

什么是好的算法，以“同步”或阵列组合成2阵列1？下面需要做的：

整数数组中2，但不是在阵列1应加入阵列1
在整数数组都可以单独留下。
整数数组1，但不是在阵列2应阵列1.

除去下面是一些文字的算法来帮助你（蟒蛇）：

def sync(a, b): 
# a is array 1 
# b is array 2 
c = a + b 
for el in c: 
    if el in b and el not in a: 
    a.append(el) # add to array 1 
    elif el in a and el not in b: 
    a.remove(el) # remove from array 1 
    # el is in both arrays, skip 
return a # done

来源

2008-12-26 22:45:16 kylebrooks

而不是“这里就是需要发生“，请尝试按照描述要求，”这里是所需的最终条件“。从这个角度看来，期望的最终状态是array1与array2完全相同的值。

如果是这样的话，为什么不等于这个伪代码（除非你的环境有clone或copy方法）？

array1 = new int[array2.length] 
for (int i in 0 .. array2.length - 1) { 
    array1[i] = array2[i] 
}

如果订购，保留重复等问题，请更新问题，我们可以再试一次。

来源

2008-12-26 23:48:45

你的问题只字未提顺序，如果你检查你的三个要求，你会看到，后置条件说ARRAY2不变和数组1现在包含完全相同的一组是在整数Array2。除非您没有告诉我们关于订单的某些要求，否则您可能只需制作Array2的副本。

来源

2008-12-27 05:57:56

“同步”2阵列的算法

回答

相关问题