0

我正在尝试编写一个算法，该算法采用可变数量的通用数组，存储在 中d_arrays，并收集其中的所有唯一元素（恰好出现一次的元素）并将它们存储在一个数组中，称为d_results. 例如，数组：

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

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

这是我当前的流程算法：

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_sizes是一个数组，其中包含 中每个数组的大小d_arrays，d_numberOfElementsInResult是 中的元素数d_results。

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

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

{ 12, 3, 7 }

现在，它根据第三个数组检查它，在它们之间产生唯一的元素。

{ 12, 7, 42, 54, 57 }

正确的？错误的。这里的问题是，由于42并且54不会出现在唯一数组中，它们最终会出现在最终产品中，即使它们对所有三个数组都是通用的。

谁能想到一个解决方案？首选对此算法进行更改，但如果这不可能，那么解决此问题的另一种方法是什么？

4

3 回答 3

2

编辑：正如所指出的，该算法是 O(nlogn) 时间和 O(n) 空间复杂度。

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

创建地图后，只需遍历它并形成计数为 1 的元素的数组。

于 2013-11-02T02:30:56.280 回答
0

解决方案1：

  1. 只需将所有数组的所有元素合二为一。
  2. 对数组进行排序
  3. 删除重复。

解决方案2：

  1. 创建一个映射，其中键是元素，值是布尔值
  2. 只需遍历单个数组。如果该元素不存在于地图中，则将键作为元素，将值作为真。但是，如果元素已经存在，则将该值设为 false。
  3. 现在只需从映射中打印其值部分为真的元素，即只出现一次。

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

众所周知，如果地图中存在键形式的元素，则表明该元素存在于数组中。因此，如果我们下次再次找到该元素时将其设为 false，则它会显示重复。希望你能理解。

于 2013-11-02T04:33:04.520 回答
0

记忆是问题，虽然我会以不同的方式做到这一点（由于缺乏经验？） - 实际上我正在考虑刚刚发布的答案！

无论如何，不​​要扔掉你的副本并将它们保存在辅助数组中。获取这个数组并将其附加到每个新数组两次，这将使您的算法几乎没有变化。唯一的变化是创建重复项并每次查看更大的列表。虽然这增加了时间和记忆。如果这是一个问题，那么请使用第一个发布的答案！

于 2013-11-02T02:45:44.860 回答