在n个数组中寻找唯一元素

Question

我试图写一个算法，它需要可变数量的通用数组，存储在d_arrays中，并收集其中所有唯一的元素（元素只发生一次），并将其存储在一个数组中，称为d_results。例如，数组：

int intA[] = { 12, 54, 42 };
int intB[] = { 54, 3, 42, 7 };
int intC[] = { 3, 42, 54, 57, 3 };

将生成包含{12,7,57}内容的数组d_结果。

以下是我当前的流程算法：

template <class T>
inline
void UniqueTableau<T>::run() {
    T* uniqueElements = d_arrays[0];
    int count = 0;
    for (int i = 1; i < d_currentNumberOfArrays; ++i) {
        if (count == 0) {
            uniqueElements = getUnique(uniqueElements, d_arrays[i], d_sizes[i - 1], d_sizes[i]);
            ++count;
        }
        else {
            uniqueElements = getUnique(uniqueElements, d_arrays[i], d_numberOfElementsInResult, d_sizes[i]);
        }
    }
    d_results = uniqueElements;
}

template <class T>
inline
T* UniqueTableau<T>::getUnique(T* first, T* second, int sizeOfFirst, int sizeOfSecond) {
    int i = 0;
    int j = 0;
    int k = 0;
    T* uniqueElements = new T[sizeOfFirst + sizeOfSecond];
    while (i < sizeOfFirst) {    // checks the first against the second
        while ((first[i] != second[j]) && (j < sizeOfSecond)) {
            ++j;
        }
        if (j == sizeOfSecond) {
            uniqueElements[k] = first[i];
            ++i;
            ++k;
            j = 0;
        } else {
            ++i;
            j = 0;
        }
    }
    i = 0;
    j = 0;
    while (i < sizeOfSecond) {    // checks the second against the first
        while ((second[i] != first[j]) && (j < sizeOfFirst)) {
            ++j;
        }
        if (j == sizeOfFirst) {
            uniqueElements[k] = second[i];
            ++i;
            ++k;
            j = 0;
        } else {
            ++i;
            j = 0;
        }
    }

    T* a = new T[k];    // properly sized result array
    for (int x = 0; x < k; ++x) {
        a[x] = uniqueElements[x];
    }

    d_numberOfElementsInResult = k;
    return a;
}

请注意，d_size是一个数组，它包含d_数组中每个数组的大小，而d_numberOfElementsInResult是d_结果中的元素数。

现在，这个数组所做的是一次比较两个元素，获取这两个元素之间的唯一元素，并将这些元素与下一个数组进行比较，依此类推。问题是，当我这样做时，有时有些元素在第三个数组和前两个数组的唯一元素之间是唯一的，但在第三个数组和第一个数组之间不是唯一的。这是一个令人困惑的词，下面是一个使用上面数组的可视化示例：

首先，该算法找到第一个和第二个数组的唯一元素。

{ 12, 3, 7 }

现在，它将根据第三个数组检查这一点，并在这些数组之间生成唯一的元素。

{ 12, 7, 42, 54, 57 }

正当错误的这里的问题是，由于42和54没有出现在唯一的数组中，因此它们最终会出现在最终产品中，即使这三个数组都是通用的。

有人能想出解决这个问题的办法吗？对该算法的修改是首选，但如果不可能，还有什么其他方法来解决这个问题？




Answer 1

解决方案1：

1. 只需将所有数组的所有元素放在一个数组中
2. 对数组进行排序
3. 删除重复项

解决方案二：

1. 创建一个映射，其中key是元素，value是布尔值

为什么我把值作为布尔值而不是整数：

我们知道，如果映射中存在键形式的元素，则表示该元素存在于数组中。因此，如果我们下次设为false，如果我们再次找到元素，它将显示为replicate。希望你能理解。

Answer 2

记忆是个问题，虽然我会用不同的方式来做这件事（因为缺乏经验？）-事实上，我在想刚刚发布的答案！

无论如何，不要丢弃副本并将其保存在辅助阵列中。将这个数组附加到每个新数组中两次，这样算法就不会有什么变化。唯一的变化是每次创建副本并查看更大的列表。虽然这增加了时间和记忆。如果这是一个问题，那么就用第一个张贴的答案！

Answer 3

编辑：正如所指出的，该算法的时间复杂度为O（nlogn），空间复杂度为O（n）。

遍历所有数组中的每个元素，并形成遍历的每个项的计数的映射。

一旦创建了映射，只需迭代它，并形成计数为1的元素数组。