消除重复元素

问题描述

小易有一个长度为n序列，小易想移除掉里面的重复元素，但是小易想是对于每种元素保留最后出现的那个。小易遇到了困难,希望你来帮助他。

输入描述

输入包括两行：
第一行为序列长度n(1 ≤ n ≤ 50)
第二行为n个数sequence[i](1 ≤ sequence[i] ≤ 1000)，以空格分隔

输出描述

输出消除重复元素之后的序列，以空格分隔，行末无空格

输入例子

9
100 100 100 99 99 99 100 100 100

输出例子

99 100

分析

首先想到将元素排序，然后用stl的unique算法把重复元素放到尾部，最后erase掉尾部。但是题目要求每种元素保留最后出现的那个，故这种方法不可行。

可以使用一个unordered_set us，从后往前把元素丢进去，这样会得到一个没有重复元素的集合，再逆序输出即可。由于unordered_set不支持反向遍历，只能再把us的元素放在vector里，再逆序输出。

note

1. 充分利用set的元素互斥性
2. 可以使用vector的反向迭代器

代码

#include <cstdio>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    scanf("%d", &n);
    vector<int> nums(n);

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &nums[i]);
    }

    vector<int> v;
    unordered_set<int> us;
    for (auto riter = nums.rbegin(); riter != nums.rend(); riter++)
    {
        int num = *riter;
        if (us.find(num) == us.end())
        {
            us.insert(num);
            v.push_back(num);
        }
    }

    printf("%d", v.back());
    for (int i = v.size() - 2; i >= 0; i--)
    {
        printf(" %d", v[i]);
    }

    return 0;
}