数据结构习题解析 2-12(c)

改进vector去重化算法，使时间复杂度为O(nlogn)，并且不改变序列中元素的相对位置。

思路：

1.保存[元素，索引(秩)]对

2.按元素用sort对向量做整体排序

3.双指针实现高效版uniquify函数（书p46)

4.按索引（秩）用sort对向量还原相对位置 *用以下lambda表达式实现按pair的第二个元素排序

sort(v.begin(),v.end(), 
    [](const pair<int, int>& a, const pair<int, int>& b)
    { return a.second < b.second; }
    );

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int>> v;
vector<pair<int,int>> res;
int siz;
void uniquify(vector<pair<int,int>>&v)
{
    int i=0;
    int j=0;

    while(++j<v.size())
    {
        if(v[i].first!= v[j].first)
            v[++i] = v[j];
    }
    siz = ++i; 
}
int main()
{
    for(int i=0;i<5;i++)
    {
        int x;
        cin>>x;
        v.push_back({x,i});
        res.push_back({0,0});
    }
    sort(v.begin(),v.end());
    uniquify(v);
    sort(v.begin(),v.end(), 
    [](const pair<int, int>& a, const pair<int, int>& b){ return a.second < b.second; }
    );
    for(int i=0;i<siz;i++)cout<<v[i].first<<" ";
}