AOJ基础题 ITP2_4_D Unique

Unique

For a sequence of integers A = {a0, a1, …, an−1} which is sorted by ascending order, eliminate all equivalent elements.

Input

A sequence is given in the following format.

n
a0 a1 , ..., an−1

Constraints

1 ≤ n ≤ 100,000
−1000,000,000 ≤ ai ≤ 1,000,000,000
a0 ≤ a1 ≤…≤ an−1

Output

Print the sequence after eliminating equivalent elements in a line. Separate adjacency elements by a space character.

Sample Input

4
1 2 2 4

Sample Output

1 2 4

問題を解く

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;

int main() {
    int n = 0;
    int m = 0;
    int b = 0;
    int e = 0;
    int k = 0;

    vector<int>a;

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> m;
        a.push_back(m);
    }

    a.erase(unique(a.begin(), a.end()), a.end());

    cout << a[0];
    for (int i = 1; i < a.size(); i++)
    {
        cout << " " << a[i];
    }
    cout << endl;

    return 0;
}

总结

很基础的题，这里需要mark一下vector里erase和unique的用法：

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

template <class ForwardIterator>
  ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return last;

  ForwardIterator result = first;
  while (++first != last)
  {
    if (!(*result == *first))  // or: if (!pred(*result,*first)) for version (2)
      *(++result)=*first;
  }
  return ++result;
}

可以看到unique()函数找的是“相邻”重复的元素，并将重复的元素放到尾部，然后返回指向第一个重复元素的迭代器；
所以使用unique之前一定要进行sort()排序，最后用erase进行删除。