Mảng trừ trừ

Question

Cách nhanh nhất để thực hiện phép trừ mảng là gì? Ví dụ:

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

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

Ở đây array sẽ là loại chương trình của tôi sử dụng để biểu diễn cấu trúc được sử dụng làm vùng chứa. Phần còn lại của nó là mã giả, tất nhiên tôi không tạo ra các mảng như thế cũng không trừ đi.

Giải pháp đơn giản nhất tôi có thể nghĩ liên quan đến vòng lồng nhau:

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

Nhưng điều này không trông rất hiệu quả. Điều gì sẽ là một cách tiếp cận khác?

Answer 1

Nếu mảng của bạn không được sắp xếp, độ phức tạp của trường hợp xấu nhất khi loại bỏ mảng sử dụng giải pháp trực quan là O (n) (mặc dù bạn có thể tăng điều này nếu sắp xếp mảng trước), vì bạn cần để kiểm tra toàn bộ mảng liệu một phần tử có tồn tại hay không.

Ví dụ về trường hợp xấu nhất:

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

Nếu mảng của bạn được sắp xếp, sau đó mức độ phức tạp thời gian trường hợp xấu nhất là 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]); 

UPDATE-Wall -Wextra -pedantic Mã 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; 
} 

Điều này sẽ r esult trong một thời gian phức tạp tồi tệ nhất của O(n+m) đối với các mảng được sắp xếp và O(n log n + m log m) đối với các mảng không được sắp xếp (sắp xếp cả hai, sử dụng hàm được cung cấp ở trên).

Answer 2

nó có thể được thực hiện trong O(nlogm + m) nơi m là mảng bạn đang trừ từ, sử dụng binary search (*) Nếu mảng không được sắp xếp, một loại sẽ là cần thiết đầu tiên mà sẽ dẫn đến O(mlogm + nlogm + m)
Pseudo code:

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 

(*) Bạn sẽ phải cung cấp cho NOT_VALID một giá trị đặc biệt cho tìm kiếm nhị phân để tiếp tục làm việc, hoặc thậm chí đơn giản hơn: duy trì một mảng mới của các yếu tố đánh dấu là NOT_VALID thay vì các yếu tố thực sự đánh dấu.

Answer 3

Nếu a1 không chứa bản sao thì bạn có thể sử dụng cấu trúc dữ liệu tập hợp băm, ví dụ: từ pblSet. Một cái gì đó như thế này:

PblSet* pSet = pblSetNewHashSet(); 

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

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

// use *ppResult 
... 

free(ppResult); 
pblSetFree(pSet); 

Hiệu suất phải là O (n + m) và mảng không cần phải được sắp xếp.

Answer 4

Bởi vì, bạn hỏi cho nhanh nhất và đơn giản nhất tôi sẽ giới thiệu một số giả định:

• số nguyên
• hữu hạn
• dương
• độc đáo
• nhỏ
• đơn đặt hàng không quan trọng.

ví dụ: bạn không có nhiều hơn 10 số. Sau đó, chúng ta hãy đối xử với họ như bộ cho một O (n) giải pháp (nơi n đại diện cho kích thước hữu hạn tối đa của tập):

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

Đối với một câu trả lời thậm chí nhiều hơn cheekier, nếu những con số trong mảng của bạn không vượt quá 0-31, bạn chỉ có thể đơn giản hóa việc sử dụng trên 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;