减去数组

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

但这看起来效率不高.另一种方法是什么？

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)非排序数组的最差时间复杂度(对两者进行排序,使用上面提供的函数).