C-C++|数组元素去重 C-C++|数据结构与算法

问题：去除数组中重复的元素。
输入：

2, 7, 3, 7, 2, 9, 9, 3

输出：

2, 7, 3, 9

思路：
1、利用数组
准备一个额外空间的数组A，遍历输入数组中的元素，每个元素都去数组A中遍历，A中存在则不管，不存在就将该元素放入数组A。
2、利用ADT
利用语言自身所带的红黑底层结构的容器，如Java的TreeSet以及TreeMap，C++的unordered_set，set。准备一个这样的结构，遍历输入数组，往容器中插入，遍历完成后，容器中的元素就是去重后的元素。这个方案的时间复杂度为O(nlogn),空间复杂度为O(n)。
利用hash结构，hashtable。
遍历每个元素，放入hash结构。这个方案的缺陷在于，随着输入规模的增大，最后hash结构会退化，导致效率下降。
拓展：记录每个元素出现的次数
3、引入排序
调用语言库排序算法
将排序手段看作一个ADT。
先将输入的数组S排序。再引入两个int变量L和R，分别指向排序后的起始下标。
R向右移动(自增)，判断S[R]和S[L]是否相等，如果相等，R继续向右移动(自增)。
S[R]与S[L]不等的时候，R - L 就是S[L]元素出现的次数。打印S[L]及 R-L 的值。L再移动到R的位置。图示如下：

文章图片

C++示例代码：

#ifndef SOLUTION_HPP #define SOLUTION_HPP #include #include using namespace std; class Solution{ public: static void unique(vector& vec) { if(vec.size() == 0) return; std::sort(vec.begin(), vec.end()); unsigned int Left = 0, Right = 0; for(; Left < vec.size(); Left = Right) { for(Right = Left + 1; Right < vec.size(); ++Right) { if(vec[Left] != vec[Right]) { break; } } cout << vec[Left] << " : " << Right - Left << endl; } }}; #endif // SOLUTION_HPP

调用示例：

#include /*#include "LinuxList.h"*/ #include "solution.hpp" //#include "commondef.hpp" #include using namespace std; int main(int argc, char *argv[]) { //UNUSED(argc); //UNUSED(argv); cout << "Hello World!" << endl; vector list = {2, 7, 3, 7, 2, 9, 9, 3}; Solution::unique(list); return 0; }

最后这个方案，使用了标准库的排序算法，时间复杂度O(n log n) 如果需要引入其他的容器来存结果的话，空间复杂度为O(n)。
【C-C++|数组元素去重】总结：