去除字符串里面的重复字母

去除字符串里面的重复字母

题目:有一个只包含大小写字母的字符串,请你去掉其中重复的字母,不改变字母原来的相对位置。

我一开始想着用遍历的方法,在vector中每添加一个字符时就遍历一次,但是效率太低。我想到两种可行的方法:

1、可以使用两个vector,第一个vector里面的元素初始化为52个空字符,然后按照字母的顺序依次向第一个vector里面添加字母,注意在向第一个vector添加元素时,判断该位置存放的字符是否为空,如果为空,就添加到第一个vector,接着再把当前的字符添加到第二个vector中。这个方法模拟了一个hash表,其中hash算法是字母在ascii表中的相对顺序。

2、直接把第一种方法的第一个vector换成set,通过每次查看set中是否存在当前元素来决定是否把当前元素插入到第二个vector中。此种方法的代码如下:

#include<iostream>
#include<string>

#include<set>
#include<vector>
using namespace std;

int main() {

    set<char>myset;
    vector<char>vec;
    string str;

    while(cin >> str){
        myset.erase(myset.begin(),myset.end());
        vec.erase(vec.begin(),vec.end());
        for (int i = 0,j=0; i < str.length(); i++){
            if(myset.insert(str[i]).second){
                vec.push_back(str[i]);
            }
        }
        for (auto &it:vec)cout << it;
        cout<<endl;
    }
    return 0;
}

由于评测系统会给出多个测试用例,所以用while循环读取输入,要注意每次读取一个测试输入都要擦除vector和set中的元素,防止上次的元素干扰。

在输出vector中的元素时,for循环使用“基于范围的for循环”,这里贴一份chatGPT给出的说明:

“C++的范围for循环是使用for关键字的一种方法,它可以更方便地遍历容器中的元素,例如数组或容器,而不需要手动迭代或使用指针。”

代码示例:

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> nums {1, 2, 3, 4, 5};

    for (auto num : nums) {
        std::cout << num << " ";
    }

    return 0;
}

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注