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 个元素)。它们没有被订购，我不应该修改它们。它们每个中的元素都是唯一的，即每个数字在每个数组中只能出现 1 次。 v2 将只包含 v1 中元素的一个子集。 实现这一目标的最有效方法是什么？

Answer 1

一种在内存方面贪婪但在 CPU 周期(线性时间)方面快速的方法是直方图，因为平凡意义上的列表比较通常使用二次执行复杂度 :(。

代码 list

---

#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 运行

---

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