题目链接|提取不重复的整数

题意：输入一个 int 型整数，按照从右向左的阅读顺序，返回一个不含重复数字的新的整数。保证输入的整数最后一位不是 0 。

数据范围： $1\le n\le 10^{8}1\backslash leq\; n\backslash leq\; 10^8$

输入描述： 输入一个int型整数

输出描述： 按照从右向左的阅读顺序，返回一个不含重复数字的新的整数

方法一：使用数组记录每个数字是否已经出现 (哈希表思想)

因为字符串的范围在0～9，最多只有10种字符。可以从右向左取出数字的每一位，并维护一个数组记录，当前数字是否已经出现。如果当前字符已经出现，该数字不输出，如果当前字符没有出现过，将记录的数组设成1，并输出当前数字。

时间复杂度：$O(N)O(N)$，解释：遍历一遍字符串的复杂度为$O(N)O(N)$。

空间复杂度：$O(M)O(M)$，解释：需要建立一个数组记录当前字符是否出现，所以复杂度是$O(M)O(\; M)$。（M是种类数）

代码

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int ans=0;
int vis[12]={0};
string str;
int main() {
    cin>>str; //按照字符串类型输入更好处理
    int len=str.length(); //数字长度
    for(int i=len-1;i>=0;i--){
        int num=(int)str[i]; //每一位
        if(vis[num]==0) {
            vis[num]=1; //将出现过的数字标记上
            cout<<str[i]; //在此之前没有出现过，所以该位可以输出
        }
    }
    cout<<endl;
    return 0;
}

方法二：使用STL中的集合来统计，输出集合中未出现过的数字

每次向集合中添加元素时，如果集合中已经有该元素，不会重复添加；如果集合中没有该元素，则会添加新元素。反向遍历数字的同时询问该数字是否已经存在于集合中，如果没有出现过，就向集合添加这个数字并输出；否则忽略该数字。在C/C++中set的实现是红黑树。

时间复杂度：$O(NlogN)O(NlogN)$, 解释：单次插入的复杂度为$O(logN)O(logN)$，操作$NN$次，所以复杂度为$O(NlogN)O(NlogN)$。

空间复杂度：$O(M)O(M)$，解释：使用树的数据结构维护节点的复杂度为$O(M)O(M)$，其中$MM$为种类数目。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
using namespace std;
string str;
set<char> nums;
int main() {
    cin>>str; //按照字符串类型输入更好处理
    int len=str.length();
    for(int i=len-1;i>=0;i--){
        if(nums.find(str[i])!=nums.end()){ //假设集合中已经出现过了就直接忽略
            continue;
        } else {
            cout<<str[i]; //否则直接输出当前数字
            nums.insert(str[i]); //将当前数字添加到集合里
        }    
    }
    cout<<endl;
    return 0;
}