C: печатать только не общие элементы в 2 массивах

Question

У меня есть код C, который я хочу изменить очень просто.

Скажем, у меня есть два массива, как этот

int v1[5] = {1, 3, 7, 13, 10}; 
    int v2[2] = {1, 10}; 

И я хотел бы, чтобы напечатать не общие элементы (разность), как:

3, 7, 13 

Вот моя попытка, которая не является еще достаточно :

#include <stdio.h> 

int main() 
{ 
    int v1[5] = { 1, 3, 7, 13, 10 }; 
    int v2[2] = { 1, 10 }; 

    for (int i = 0; i < sizeof(v1)/(sizeof * v1); i++) { 
     for (int j = 0; j < sizeof(v2)/(sizeof * v2); j++) { 
      if (v1[i] != v2[j]) { 
       printf("%d ", v1[i]); 
       break; 
      } else { 
       break; 
      } 
     } 
    } 

    return 0; 
} 

Два массива всегда будут очень короткими (не более 6 элементов). Thery не упорядочены, и я не должен их изменять. Элементы в каждом из них уникальны, каждый номер может появляться только один раз в каждом массиве. v2 будет содержать только подмножество элемента из v1. Что было бы самым эффективным способом достижения этого?

Answer 1

Вы можете начать с принятия любого массива и итерации его элементом по элементу и определения того, находится ли этот элемент во втором массиве также вложенным циклом и помещает условие if во внутренний цикл for и сохраняет общий элемент в другом массиве а затем сравнивая оба массива один за другим с этим массивом и помещая необычный элемент в другой массив.

Как:

int a[min(l1,l2)], b[l], x = 0, k = 0, flag = 1; 
for(int i=0; i<l1; i++){ 
for(int j=0; j<l2; j++){ 
    if(v1[i]==v2[j]){ 
     a[k] = v1[i]; 
     k++; 
    } 
} 
} 
for(int i=0; i<l1; i++){ 
flag = 1; 
for(int j=0; j<k; j++){ 
    if(v1[i] == a[j]){ 
     flag = 0; 
     break; 
    } 
} 
if(flag==1){ 
    b[x] = v1[i]; 
    x++; 
} 
} 

for(int i=0; i<l2; i++){ 
flag = 1; 
for(int j=0; j<k; j++){ 
    if(v2[i] == a[j]){ 
     flag = 0; 
     break; 
    } 
} 
if(flag==1){ 
    b[x] = v2[i]; 
    x++; 
} 
} 

После этого вы можете распечатать массив.

Answer 2

Подход, который является жадным с точки зрения памяти, но быстрым с точки зрения циклов ЦП (линейное время) является гистограммой, поскольку сравнения списков в тривиальном смысле обычно используют квадратичную сложность выполнения :(.

Листинг

---

#include <errno.h> 
#include <stdio.h> 
#include <stdint.h> 
#include <stdlib.h> 
#include <time.h> 

int main(void) { 

    /* Allocate. */ 
    int numElements1 = 0; 
    int numElements2 = 0; 

    const int maxHistVal = UINT8_MAX + 1; 
    const int maxElements = 10; 
    const int minElements = 1; 
    uint8_t *arr1 = NULL, *arr2 = NULL; 
    uint8_t *histogram = NULL; 

    /* Init random seed. */ 
    srand(time(NULL)); 

    /* Determine number of elements for each array. */ 
    numElements1 = (rand() % (maxElements - minElements)) + minElements; 
    numElements2 = (rand() % (maxElements - minElements)) + minElements; 

    /* Generate two random arrays with non-duplicated values. */ 
    if (NULL == (arr1 = calloc(numElements1, sizeof(uint8_t)))) { 
     return ENOMEM; 
    } else if (NULL == (arr2 = calloc(numElements2, sizeof(uint8_t)))) { 
     free(arr1); 
     return ENOMEM; 
    } else if (NULL == (histogram = calloc(maxHistVal, sizeof(uint8_t)))) { 
     free(arr2); 
     free(arr1); 
     return ENOMEM; 
    } else { 
     /* Have our sample arrays and histogram. Populate them and print them 
     * out. 
     */ 
     printf("ARR1: "); 
     uint8_t j = 0; 
     for (int i = 0, j = 0; i < numElements1; i++) { 
      /* Populate array. */ 
      j += (rand() % 2) + 1; 
      arr1[i] = j; 
      printf("%-3d ", arr1[i]); 
      /* Update histogram. */ 
      histogram[arr1[i]]++; 
     } 
     printf("\n"); 
     printf("ARR2: "); 
     for (int i = 0, j = 0; i < numElements2; i++) { 
      /* Populate array. */ 
      j += (rand() % 2) + 1; 
      arr2[i] = j; 
      printf("%-3d ", arr2[i]); 
      /* Update histogram. */ 
      histogram[arr2[i]]++; 
     } 
     printf("\n"); 
     /* Print out only values that appear exactly once in the histogram. */ 
     printf("HISTOGRAM: UNIQUE VALUES: "); 
     for (int i = 0, j = 0; i < maxHistVal; i++) { 
      /* Print histogram. */ 
      if (1 == histogram[i]) { 
       printf("%-3d ", i); 
      } 
     } 
     printf("\n"); 
     /* For fun, identify the duplicates. */ 
     printf("HISTOGRAM: DUPLICATE VALUES: "); 
     for (int i = 0, j = 0; i < maxHistVal; i++) { 
      /* Print histogram. */ 
      if (1 < histogram[i]) { 
       printf("%-3d ", i); 
      } 
     } 
    } 

    /* Cleanup..*/ 
    free(histogram); 
    free(arr2); 
    free(arr1); 

    return 0; 
} 

Sample Run

---

ARR1: 2 3 4 6 8 9 10 
ARR2: 1 2 3 4 
HISTOGRAM: UNIQUE VALUES: 1 6 8 9 10 
HISTOGRAM: DUPLICATE VALUES: 2 3 4 

Answer 3

#include <stdio.h> 

#define NMEMBERS(x) ((sizeof(x))/(sizeof *(x))) 

int main() 
{ 
    int v1[] = { 1, 3, 7, 13, 10 }; 
    int v2[] = { 1, 10 }; 
    char common[6] = {0}; 
    int i, j; 

    for (i = 0; i < NMEMBERS(v1); i++) { 
     for (j = 0; j < NMEMBERS(v2) && v1[i] != v2[j]; j++); 
     if (NMEMBERS(v2) == j) 
      printf("%d ", v1[i]); 
     else 
      common[j] = 1; 
    } 
    for (j = 0; j < NMEMBERS(v2); j++) { 
     if (!common[j]) 
      printf("%d ", v2[j]); 
    } 

    return 0; 
} 

Answer 4

Что будет наиболее эффективным способом для достижения этой цели?

В случае, если диапазон значений в a[], b[] быть ограничено 0 до 63, код может использовать unsigned long long маску.

Это повторяется через каждый массив l1 + l2 операций, а не двойной цикл for() с l1 * l2 операций.

#include <assert.h> 
#include <stdio.h> 

int main(void) { 
    const int v1[5] = { 1, 3, 7, 13, 10 }; 
    const int v2[2] = { 1, 10 }; 

    unsigned long long mask = 0; 
    for (size_t i = 0; i < sizeof(v2)/(sizeof *v2); i++) { 
    assert(v2[i] >= 0 && v2[i] < 64); 
    mask |= 1ull << v2[i]; 
    } 
    mask = ~mask; 
    for (size_t i = 0; i < sizeof(v1)/(sizeof *v1); i++) { 
    assert(v1[i] >= 0 && v2[i] < 64); 
    if ((1ull << v1[i]) & mask) { 
     printf(" %d", v1[i]); 
    } 
    } 
    puts(""); 
    return 0; 
} 

Выход

3 7 13