算法

C++算法题-独特顺序

来自 codewar 的一道题目。

Implement the function unique_in_order which takes as argument a sequence and returns a list of items without any elements with the same value next to each other and preserving the original order of elements.

For example:

1
2
3

uniqueInOrder("AAAABBBCCDAABBB") == {'A', 'B', 'C', 'D', 'A', 'B'}
uniqueInOrder("ABBCcAD")         == {'A', 'B', 'C', 'c', 'A', 'D'}
uniqueInOrder([1,2,2,3,3])       == {1,2,3}

给一系列的数据，要返回一个没有相同元素且和原顺序一样的 vector 数据。

1
2
3
4
5
6
7
8
9

#include <string>
#include <vector>

template <typename T> std::vector<T> uniqueInOrder(const std::vector<T>& iterable){
  //your code here
}
std::vector<char> uniqueInOrder(const std::string& iterable){
  //your code here
}

题解

需要注意的是提供的代码中有 typename T ，这是一个模板类型参数。T 可以是任意类型只要该类型能用于实例化 std::vector<T>。
模板是一个很强大的工具，可以编写更通用的代码出来。

提供了两个函数块，第一个为通用，而第二个将 string 单独列出来。实际上两者只在最初有所不同。
首先，发现 iterable 被 const 常量修饰。即还需要创建一个用于修改并返回的 vector 类型变量，而两个函数的差别也就在这。
对于 typename T 只需要赋值即可：

1

    std::vector<T> res = iterable;

而对于 string 因为两者类型不同，需要将单独元素一一放置，使用迭代器循环

1
2
3
4

std::vector<char> res;
for (auto it : iterable) {
    res.emplace_back(it);
}

接下来去掉重复元素和 C++算法题-寻找相同元素 该题一样，现在就可以轻车熟路地运用了。:
两个函数一致:

1
2
3

auto it = std::unique(res.begin(), res.end());
res.erase(it, res.end());
return res;

最终答案:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

#include <algorithm>
#include <string>
#include <vector>

template <typename T>
std::vector<T> uniqueInOrder(const std::vector<T>& iterable) {
    std::vector<T> res = iterable;
    auto it = std::unique(res.begin(), res.end());
    res.erase(it, res.end());
    return res;
}

std::vector<char> uniqueInOrder(const std::string& iterable) {
    std::vector<char> res;
    for (auto it : iterable) {
        res.emplace_back(it);
    }
    auto it = std::unique(res.begin(), res.end());
    res.erase(it, res.end());
    return res;
}

其他题解

实际上在 c++ 已经有非常好用的现成函数了，它就是 unique_copy()

1

std::unique_copy(IIter, IIter, OIter)

该函数位于 <algorithm> 头文件内。使用方法为:

1

unique_copy (iterable.begin(), iterable.end(), std :: back_inserter(res));

实际就是遍历 iterable 如果发现该元素不重复就直接在 res 后面插入该元素。

除此之外，还有用循环判断的方式来选择，比我的做法更简洁：

1

for (const auto& c : iterable) if (result.empty() || c != result.back()) result.push_back(c);

c != result.back() 可以避免连续重复的元素，但是不是在 result 内完全的去重。

萌ICP备20241614号