数组和已知子序列差分的有效算法？

Question

我传递一个数组到一个库函数，它返回一个数组，它是输入数组的子序列。也就是说，第一和第二阵列的顺序是相同的，但是第二阵列可能缺少第一阵列的任何数量的元素。在两个阵列中都不会有重复！

我想然后构建一个新的数组中的所有元素，这些元素在输入中但不在函数的输出中。

由于某些原因，虽然听起来微不足道，但我仍然认为它错了，特别是在它看起来像数组的末尾。

实施例1（典型）：

输入阵列的：

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, ios, app, tlv, lcy ] 

输入数组b：

[ yyz, ltn, tse, uln, ist, gva, doh, hhn, vlc, tlv, lcy ] 

输出数组 “差别”：

[ ios, app ] 

实施例2（最小，显示一些错误当该差值在字符串的末尾）：

输入阵列的：

[ usa ] 

输入数组b：

[ ] 

输出数组 “差别”：

[ usa ] 

（我将在JavaScript/jQuery中实现它，但我更感兴趣的是伪代码中的泛型算法，因为我实际上是处理对象数组。所以请我正在寻找专门使用数组索引的算法，而不是像我在C/C++中那样的指针）

Answer 1

作为第二阵列b是第一阵列具有相同顺序的的一个子集，可以在平行行走两​​者比较的电流值，并采取的一个当前值，如果它是从b的电流值不同：

var a = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','ios','app','tlv','lcy'], 
    b = ['yyz','ltn','tse','uln','ist','gva','doh','hhn','vlc','tlv','lcy'], 
    diff = []; 
var i=0, j=0, n=a.length, m=b.length; 
while (i<n && j<m) { 
    if (a[i] !== b[j]) { 
     diff.push(a[i]); 
    } else { 
     j++; 
    } 
    i++; 
} 
while (i<n) { 
    diff.push(a[i++]); 
} 

或者，如果你愿意只有一个while循环：

// … 
while (i<n) { 
    if (j<m && a[i] === b[j]) { 
     j++; 
    } else { 
     diff.push(a[i]); 
    } 
    i++; 
} 

Answer 2

在java中我可能会这样做，如果我想使用数组。你将不得不循环所有你返回的对象，你将不得不将它们与你发送的所有对象进行比较，这样你在最坏的情况下会有一个O（n^2）复杂度，但是，你可能可能通过对发送的列表进行排序并使用指针来检查每个位置（但由于您不想使用指针，所以我将这个示例保留），从而改进这一点，那么您可以将它与O（n）进行比较。

public void doYourJob(){ 
     Object[] allObjects = new Object[10]; //hold all original values 
     Object[] recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one 
     Object[] missingArray = new Object[allObjects.length - recivedArray.length]; 
     for(Object inObj : allObjects){ 
      boolean foundObject = false; 
      for(Object obj : recivedArray){ 
       if(inObj.equals(obj)){ 
        foundObject = true; 
        break; 
       } 
      } 
      if(!foundObject) 
       missingArray add inObj //add the missing object. This is not correct java code. =) 
     } 
    } 

如果我大声地用从Collection接口的东西那么这将是简单得多，因为你可以使用“myArray.contains（）”方法。

随着解释代替

public void doYourJob(){ 
     List<Object> allObjects = new ArrayList<Object>(); //hold all original values 
     List<Object> recivedArray = yourBlackBox(allObjects); //send in the array an gets the smaller one 
     List<Object> missingArray = new ArrayList<Object>(); 
     for(Object inObj : allObjects){ 
      if(!recivedArray.contains(inObj)) 
       missingArray.add(inObj); 
     } 
    } 

Answer 3

你有一个保证有序强加给你的阵列？如果是的话，应该是比较简单的做一些事情，如：

# our inputs are array1 and array2, array2 is the one with 0 or more missing elements 
ix1 = 0 
ix2 = 0 
diff = new array 
while ix2 < length(array2) 
    while (ix1 < length(array1)) and (array1[ix1] != array2[ix2]) 
    add array1[ix1] to diff 
    ix1 = ix1 + 1 
    ix1 = ix1 + 1 
    ix2 = ix2 + i 

return diff 

如果没有排序，你可以并处一（两个数组排序），或者你可以使用一个哈希表。

hash = new hash 
diff = new array 

for each element in array1 
    hash[element] = 1 

for each element in array2 
    hash[element] = hash[element] + 1 

for each key in hash 
    if hash[key] == 1 
    add hash[key] to diff 

这两种应该（大致）为O（n）中，如果（且仅当）将一个元素增加到阵列是O（1）（如果翻倍的结果阵列的大小，每次运行在它充满了，至少渐近地O（1））。