由网友(简单好听的豆瓣名字 好听的豆瓣昵称大全)分享简介：什么是实现阵列减法一个最快的方法是什么？例如：What's a fastest way to implement array subtraction? For example:array a1 = [1, 3, 4, 5, 8];array a2 = [2, 4, 5];array a3 = a1 - a2; /...

什么是实现阵列减法一个最快的方法是什么？例如：

What's a fastest way to implement array subtraction? For example:

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

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

下面阵列将是我的程序使用，以重新present这是作为一个容器中的结构类型。它的其余部分是伪code，我当然没有创造一样，也不是阵列减法。

Here array would be the type my program uses to represent a struct which is used as a container. The rest of it is pseudo code, of course I'm not creating the arrays like that nor subtracting.

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

The simplest solution I can think of involves nested loops:

/* 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];
}

但是，这看起来不是很有效。什么是另一种方法？

But this does not look very efficient. What would be another approach?

推荐答案

如果您的数组进行排序，使用直观的解决方案的最坏情况下的时间复杂度为数组排除是O（n 2 ）（虽然你可以提高这个，如果你的数组排序第一），因为你需要检查整个数组中的元素是否存在与否。

If your arrays aren't sorted, the worst case time complexity for an array exclusion using a intuitive solution is O(n2) (although you can boost this if you sort the arrays first), since you need to check the whole array whether an element is existent or not.

最坏的情况下的示例：

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

如果你的阵列是有序的，那么最坏情况下的时间复杂度为O（N + M）（伪code）：

If your arrays are ordered, then the worst case time complexity is O(n+m) (pseudo-code):

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 code：

UPDATE -Wall -Wextra -pedantic C code:

#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日志N + M登入）非有序阵列（排序两种，使用上面所提供的功能）。

This will result in a worst time complexity of O(n+m) for sorted arrays and O(n log n + m log m) for non-sorted arrays (sort both, use the function provided above).