删除字符串算法中的重复项

Question

我的作业是删除随机字符串中的重复项。我的想法是使用 2 个循环来解决问题。

第一个将扫描字符串中的每个字符。 第二个将检查字符是否重复。如果是这样，请删除该字符。

string content = "Blah blah..."

    for (int i = 0; i < content.size(); ++i) {
            char check = content.at(i);
            for (int j = i + 1; j < content.size() - 1; ++j) {
                if (check == content.at(j)) {
                    content.erase(content.begin()+j);

                }
            }
        }

问题是它不起作用。它总是删除错误的字符。似乎是索引问题，但我不明白为什么。

临时修复是将

content.erase(content.begin()+j);

更改为

content.erase(                        remove(content.begin() + i+1, content.end(), check),content.end());

但我认为触发“按值删除”扫描不是一个好方法。我想用 2 个或更少的循环来完成它。

任何想法将不胜感激:)

Answer 1

你的循环看起来像下面这样

#include <iostream>
#include <string>

int main() 
{
    std::string s = "Blah blah...";

    std::cout << '\"' << s << '\"' << std::endl;

    for ( std::string::size_type i = 0; i < s.size(); i++ )
    {
        std::string::size_type j = i + 1;
        while ( j < s.size() )
        {
            if ( s[i] == s[j] )
            {
                s.erase( j, 1 );
            }
            else
            {
                ++j;
            }
        }
    }

    std::cout << '\"' << s << '\"' << std::endl;

    return 0;
}

输出为

"Blah blah..."
"Blah b."

还有许多其他使用标准算法的方法。例如

#include <iostream>
#include <string>
#include <algorithm>
#include <iterator>

int main() 
{
    std::string s = "Blah blah...";

    std::cout << '\"' << s << '\"' << std::endl;

    auto last = s.end();

    for ( auto first = s.begin(); first != last; ++first )
    {
        last = std::remove( std::next( first ), last, *first );
    }

    s.erase( last, s.end() );

    std::cout << '\"' << s << '\"' << std::endl;

    return 0;
}

输出与前面的代码示例相同

"Blah blah..."
"Blah b."

Answer 2

如果使用 STL 是一种可能的选择，您可以使用

std::unordered_set

来保留到目前为止看到的字符，并使用

std::remove_if

擦除 - 删除成语，如下例所示：

#include <iostream>
#include <string>
#include <unordered_set>
#include <algorithm>

int main() {
  std::string str("Hello World!");
  std::unordered_set<char> log;
  std::cout << "Before: " << str << std::endl;
  str.erase(std::remove_if(str.begin(), str.end(), [&] (char const c) { return !(log.insert(c).second); }), str.end());
  std::cout << "After:  " << str << std::endl;
}

现场演示

Answer 3

我建议采用两次通过的方法。第一遍识别重复字符的位置；第二遍删除它们。

我建议使用

std::set

和

std::vector<unsigned int>

。该向量包含字符串中的字母。该向量包含重复字母的位置。

第一遍检测集合中是否存在字母。如果该字母存在，则将该位置附加到向量中。否则，该字母被插入到集合中。

对于第二遍，按降序对向量进行排序。
擦除向量中位置处的字符，然后从向量中删除该位置。

通过从字符串末尾往前擦除字符，当字符从字符串中擦除时，剩余重复项的位置不会改变。

Answer 4

我不确定这是导致您问题的原因，但我在您的代码中看到的另一个问题是在您的第二个 for 循环中。你的

j < content.size() - 1

声明应该只是

j < content.size()

。

一开始看这个原因有点棘手，但在这种情况下，您不仅仅是让向量的大小作为大小，而是作为字符串的结束索引。您正在将最后一个索引缩短一个，这意味着您不会命中字符串中的最后一个字符。我不知道这是否会帮助您解决最初的问题，但谁知道呢？

Answer 5

注意：您的实际问题是维护下一个相关元素的正确索引：

• 如果不删除一个字符，则下一个元素在下一个位置。
• 如果删除一个字符，下一个元素将移动到当前位置的位置（位置保持不变）。

此外：还有更有效的解决方案（例如：利用集合）

Answer 6

先排序

然后

unique

将所有唯一字符移动到开头并返回尾后迭代器。

然后

erase

无用的字符

string digits("1a2b3c3c2b1a");
sort(digits.begin(), digits.end());
digits.erase( unique( digits.begin(), digits.end() ), digits.end() );
cout << digits << endl;

输出

123abc