有序数组去重

Unique Elements

专题: Algorithmic Programming / 算法编程
难度: L4
来源: QuantQuestion

题目详情

给定一个长度为 $n$ 的已排序数组，抽取其中不重复的元素。

例如 [1,1,3,3,5,5,5,9,9,9,9] => [1,3,5,9]。

Given sorted array of size $n$ , extract unique items. E.g. [1,1,3,3,5,5,5,9,9,9,9] => [1,3,5,9].

解析

从左到右扫描，仅当当前元素与前一个不同才加入结果：

template<class T> vector<T> unique(T a[], int n){
  vector<T> vec;
  vec.reserve(n);
  vec.push_back(a[0]);
  for(int i=1; i<n; i++){
    if(a[i]!=a[i-1]) vec.push_back(a[i]);
  }
  return vec;
}

Original Explanation

template<class T> vector<T> unique(T a[], int n){
    vector<T> vec; 
    vec.reserve(n);
    vec.push_back(a[0]);
    for(int i=1; i<n; i++){
        if(a[i]!=a[i-1])
            vec.push_back(a[i]);
    }
    return vec;
}