c++ - 方法问题: Deleting duplicate chars in an array

Question

所以我试图删除部分填充数组中的重复字符。该数组是从位于我的 PC 上的文件填充的。我的数组填充方法工作正常；但是，我的重复删除方法不是。这是我的方法:

    void deleteRepeated(char array[], int* numberUsed)
{
    for (int x = 0; x < *numberUsed ; x++) 
    {
        cout << "Positions used: " << *numberUsed << endl;
        for (int y = x+1; y < *numberUsed; y++ )
        {
            cout << "Positions used: " << *numberUsed << endl;
            if (array[y] == array[x])
            {
                cout << "Positions used: " << *numberUsed << endl;
                for (int z = y; z < *numberUsed; z++)
                    array[z] = array[z+1];
                y--; 
                *numberUsed--;
                cout << "Positions used: " << *numberUsed << endl;
            }
        }
    }
}

我正在传递整个数组，以及该数组中使用的索引数。数组长度为 10，在我的测试中，我使用了这 10 个字符中的 6 个字符:{'g'、'g'、'n'、'o'、'r'、'e'}。我做错了什么？

注意:"cout << "Positions used: "<< *numberUsed << endl"用于检查该方法是否正确删除。在索引为 z 的最内层循环中，方法开始变得疯狂。

如有任何帮助，我们将不胜感激。

Answer 1

(我在阅读您关于不允许使用 STL 的评论之前写了这个答案的第一部分，但无论如何我都会保留它，因为我认为它是相当简洁的代码。)

您可以使用 C++ 标准库为您提供的功能。使用 std::string 而不是 char 数组(这几乎总是一个好主意)，然后您可以执行以下操作(注意:C++11 仅因为 unordered_set 和std::begin):

#include <string>
#include <unordered_set>
#include <iostream>
#include <iterator>

std::string uniquechars(const std::string& s) {
    std::unordered_set<char> uniquechars(std::begin(s), std::end(s));
    std::string newstring(std::begin(uniquechars), std::end(uniquechars));
    return newstring;
}

int main() {
    std::string teststr("thisisanexamplesentence");
    std::cout << "The unique characters of " << teststr << " are " << uniquechars(teststr) << std::endl;
}

请注意，它不会保留字符的原始顺序，因此如果需要的话，这将不起作用。

---

如果您必须在没有标准库的情况下工作，则必须更深入地挖掘。上面的@TimChild 已经很好地开始诊断您的程序出了什么问题，但是还有更有效的解决方案，例如，记录您已经看到的字符。当你使用 chars 时，我会考虑一个可以保存标记的位域(额外开销 256/8=32 字节)或者如果这不是太多，只是一个简单的数组 bool 值(额外开销 256 字节)。由于后者更容易实现并且代码更清晰:

void deleteRepeated(char array[], int *numused) {
    bool seenthischar[256] = {false};
    char *readpointer = &array[0];
    char *writepointer = &array[0];
    int length = *numused;
    for ( ;readpointer <= &array[0] + length; readpointer++) {
      if (seenthischar[((unsigned char) *readpointer)]) {
        *numused--;
      } else {
        seenthischar[((unsigned char) *readpointer)] = true;
        *writepointer = *readpointer;
        writepointer++;
      }
    }
}

这只有一个循环，所以它只需要遍历一次数组，即它的时间复杂度与输入数组的长度成线性关系。