3

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

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

出于某种原因，虽然这听起来微不足道，但我一直弄错了，尤其是在数组的末端。

示例 1（典型）：

输入数组 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 ]

输出数组“差异”：

[ ios, app ]

示例 2（最小，当差异位于字符串末尾时会显示一些错误）：

输入数组 a：

[ usa ]

输入数组 b：

[ ]

输出数组“差异”：

[ usa ]

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

4

3 回答 3

3

由于第二个数组b是第一个数组a具有相同顺序的子集，因此您可以并行行走，比较当前值，如果 a 的当前值与b的当前值不同，则取a的当前值：

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++;
}
于 2011-12-29T09:40:03.413 回答
0

在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);
        }
    }
于 2011-12-29T09:28:16.257 回答
0

您的阵列是否有保证的排序？如果是这样，执行以下操作应该相对简单：

# 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))。

于 2011-12-29T09:40:37.693 回答