减去数组

Question

有什么最快的方法来实现数组相减？例如：

array a1 = [1, 3, 4, 5, 8];
array a2 = [2, 4, 5];

array a3 = a1 - a2; /* [1, 3, 8] */

这里array是我的程序用来表示作为容器的结构体的类型。其他部分是伪代码，当然我不会像那样创建数组，也不会进行减法运算。

我能想到的最简单的解决方案涉及嵌套循环：

/* a1 - a2 */
for (i = 0; i < a1.size; ++i) {
    int is_the_same = 0;
    for (j = 0; i < a2.size; ++j)
        if (a1[i] == a2[j]) {
            is_the_same = 1;
            break;
        }
    }
    if (!is_the_same)
       a3.push a1[i];
}

但这似乎不太高效。还有其他方法吗？

- winck

---

我恐怕这是唯一的方法。除非你有排序数组，你总是可以移动“起始点”并从 j = something 开始... - Vyktor

Answer 1

如果你的数组没有排序，使用直观方法进行数组排除操作的最坏时间复杂度为O(n²)（尽管如果首先对数组进行排序，可以提高效率），因为你需要检查整个数组是否存在某个元素。

最坏情况示例：

array a1 = [1, 3, 4, 5, 8];
array a2 = [8, 5, 4, 3, 1];

如果你的数组是有序的，那么最坏情况的时间复杂度是O(n+m)（伪代码）:

int i = 0;
for(int j = 0; i < a1.size && j < a2.size;){
    if(a1[i] == a2[j])
        ++i, ++j;  // exclude this element
    if(a1[i] < a2[j]){
         a3.push(a1[i]); // include this element
         ++i;
    }
    if(a1[i] > a2[j])
         ++j; // ignore lesser elements
}
while(i < a1.size)
     a3.push(a1[i]);

更新 -Wall -Wextra -pedantic 的C代码：

#include <stdio.h>
#include <malloc.h>

/**
* The following function excludes values from an array using another arrays values.
* Note that this version won't exclude multiple values, for this you have to drop
* '++j' in line 25.
*
* \param[in] from Original sorted array
* \param[in] from_length Original array length
* \param[in] what Sorted array including the excluding values
* \param[in] what_length self describing
* \param[out] result_length the lenght of the new array - a value lesser 0 indicates an error.
*/

int* exclude(int* from, int from_length, int* what, int what_length, int* result_length){
    int i,j,k;
    int* result = (int*) malloc(sizeof(int)*from_length);
    if(result == NULL){
        *result_length = -1;
        return NULL;
    }
    for(i = j = k = 0; i < from_length && j < what_length;){
        if(from[i] == what[j])
            ++i, ++j;  /* exclude this element - to enable multiple exclusion drop '++j' 
                        4,4,5,6 /4 --> 5,6 */
        if(from[i] < what[j])
            result[k++] = from[i++];
        if(from[i] > what[j])
             ++j; /* ignore lesser elements */
    }
    while(i < from_length)
        result[k++] = from[i++];

    if( k < from_length){
        int* tmp = (int*) realloc(result,sizeof(int)*k);
        if(tmp == NULL){
            /* either error handling or returning result */
        }else{
            result = tmp;
        }
    }
    *result_length = k;
    return result;
}

int main(){
    int a[6] = {1,2,3,4,5,6};
    int b[3] = {2,4,5};
    int result_length;
    int i;
    int *c = exclude(a,6,b,3,&result_length);
    for(i = 0; i < result_length; ++i)
        printf("%i ",c[i]);
    free(c);
    return 0;
}

对于已排序的数组，最坏时间复杂度为O(n+m)，对于未排序的数组，最坏时间复杂度为O(n log n + m log m)（将两个数组都排序，使用上面提供的函数）。

- Zeta

---

+1 Zeta。我开始着手解答，经过改进后，最终成为了你的_O(n+m)_答案的副本，只不过你的版本更好。 - Stephen Quan

Answer 2

可以使用二分查找，在O(nlogm + m)的时间复杂度内完成操作，其中m是你要从中减去的数组。 (*)如果数组未排序，则需要先进行排序，这将导致O(mlogm + nlogm + m)的时间复杂度。
伪代码：

remove(a1,a2): //a1-a2
   for each element x in a2:
      i <- binarySearch(a1,x)
      if x is in a1:
         a1[x] <- NOT_VALID
   remove all elements in a1 marked NOT_VALID

(*) 你需要给NOT_VALID赋一个特殊值，以便二分查找继续工作，或者更简单的方法是：维护一个新的元素数组，标记为NOT_VALID，而不是实际标记元素。

- amit

Answer 3

如果a1不包含重复项，则可以使用哈希集数据结构，例如来自pblSet。类似这样的代码：

PblSet* pSet = pblSetNewHashSet();

pblSetAddAll(pSet, a1);
pblSetRemoveAll(pSet, a2);

int** ppResult = (int**) pblSetToArray(pSet);

// use *ppResult
...

free(ppResult);
pblSetFree(pSet);

性能应该是O(n + m)，而且数组不需要排序。

- richj

Answer 4

因为您要求最快和最简单的方法，所以我会做一些假设：

• 整数
• 有限的
• 正数
• 唯一的
• 小的
• 顺序不重要。

例如，您最多只有10个数字。那么我们可以将它们视为集合，使用O(n)的解决方案（其中n表示集合的最大有限大小）：

// Initialize array1 to [1, 3, 4, 5, 8].
unsigned char array1[10];
memset(array1, 0, 10);
array1[1] = 1;
array1[3] = 1;
array1[4] = 1;
array1[5] = 1;
array1[8] = 1;

// Initialize array2 to [2,4,5].
unsigned char array2[10];
memset(array2, 0, 10);
array2[2] = 1;
array2[4] = 1;
array2[5] = 1;

// Implement array3 = array1 - array2.
unsigned char array3[10];
memset(array3, 0, 10);
for (int i = 0; i < 10; i++)
    array3[i] = array1[i] & ~array2[i];

如果你的数组中的数字不超过0-31，为了得到更加简洁的答案，你可以使用unsigned int来简化上述过程：

    // array1 = 1, 3, 4, 5, 8
    unsigned int array1 = (1 << 1) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 8);
    // array2 = 2, 4, 5
    unsigned int array2 = (1 << 2) | (1 << 4) | (1 << 5);
    // array3 = array1 - array2;
    unsigned int array3 = array1 &~ array2;

- Stephen Quan

---

使用桶方法和修订版4。如果array1是密集的，使用位存储布尔值数组的版本将比我的快8倍。然而，数组的解释将使用相同的常量... - Zeta

感谢Zeta。我刚刚添加了一个狡猾的位运算解决方案到答案中。通常，在早期计算中，位解决方案非常受欢迎。O（n），O（n / 8）和O（n / 32）在技术上是相同的复杂度，因为常数因素被隐藏了。 - Stephen Quan