c++学习笔记
-
用vector和unique删除重复元素
我们都知道unique的功能是去除相邻的重复元素(只保留一个),还有一个容易忽视的特性是它并不真正把重复的元素删除,不知道这个特性用起来就会出问题。比如下面这个例子,企图输出无重复的元素,
#include <iostream> #include <vector> #include <algorithm> #include <iterator> using namespace std; int main()...{ vector<int> ivec; copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(ivec)); sort(ivec.begin(),ivec.end()); unique(ivec.begin(),ivec.end()); copy(ivec.begin(),ivec.end(),ostream_iterator<int>(cout," ")); system("pause"); return 0; }
如果输入3 2 1 1 2 3,它的输出是1 2 3 2 3 3——没到达要求。
unique只是把重复的元素放到容器的后面,而它本身会返回一个迭代器,只向这些元素的开始部分。因此要向真正删除这些元素,还是要“手工”处理一下。对于上面的例子,可以用vector窗口的erase:
int main() { vector<int> ivec; copy(istream_iterator<int>(cin),istream_iterator<int>(),back_inserter(ivec)); sort(ivec.begin(),ivec.end()); vector<int>::iterator iter=unique(ivec.begin(),ivec.end()); ivec.erase(iter,ivec.end()); copy(ivec.begin(),ivec.end(),ostream_iterator<int>(cout," ")); system("pause"); return 0; }
STL equal_range用法
equal_range是C++ STL中的一种二分查找的算法,试图在已排序的[first,last)中寻找value,它返回一对迭代器i和j,其中i是在不破坏次序的前提下,value可插入的第一个位置(亦即lower_bound),j则是在不破坏次序的前提下,value可插入的最后一个位置(亦即upper_bound),因此,[i,j)内的每个元素都等同于value,而且[i,j)是[first,last)之中符合此一性质的最大子区间
如果以稍许不同的角度来思考equal_range,我们可把它想成是[first,last)内"与value等同"之所有元素形成的区间A,由于[fist,last)有序(sorted),所以我们知道"与value等同"之所有元素一定都相邻,于是,算法lower_bound返回区间A的第一个迭代器,算法upper_bound返回区间A的最后一个元素的下一个位置,算法equal_range则是以pair的形式将两者都返回
即使[fist,last)并未含有"与value等同"之任何元素,以上叙述仍然合理,这种情况下,"与value等同"之所有元素形成的,其实是一个空区间,在不破坏次序的情况下,只有一个位置可以插入value,而equal_range所返回的pair,其第一和第二(都是迭代器)皆指向该位置。
e.g:
给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { vector<vector<int>> result; if(nums.size() < 4) return result; sort(nums.begin(), nums.end()); unordered_multimap<int , pair<int, int>> cache; for (int i = 0; i < nums.size()-1; i++) { for (int j = i+1; j < nums.size(); j++){ cache.insert(make_pair(nums[i] + nums[j], make_pair(i, j))); } } for (auto i = cache.begin(); i != cache.end(); i++){ int gap = target - i->first; auto range = cache.equal_range(gap); for ( auto j = range.first; j != range.second; j++){ int a = i->second.first; int b = i->second.second; int c = j->second.first; int d = j->second.second; if(a != c && a != d && b !=c && b!=d){ vector<int> tmp = { nums[a], nums[b], nums[c], nums[d]}; sort(tmp.begin(), tmp.end()); result.push_back(tmp); } } } sort(result.begin(), result.end()); result.erase(unique(result.begin(), result.end()), result.end()); return result; } };
数组去重
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn’t matter what you leave beyond the new length.// 使用remove()时间复杂度 O(n) 空间复杂度O(1) class Solution { public: int removeElement(vector<int>& nums, int target) { return distance(nums.begin(), remove(nums.begin(), nums.end(), target)); } };
堆排序原理与实现(小顶堆)
堆排序实际上是利用堆的性质来进行排序的,要知道堆排序的原理我们首先一定要知道什么是堆。
堆的定义:
堆实际上是一棵完全二叉树。
堆满足两个性质:
1、堆的每一个父节点都大于(或小于)其子节点;
2、堆的每个左子树和右子树也是一个堆。堆的分类:
堆分为两类:
- 最大堆(大顶堆):堆的每个父节点都大于其孩子节点;
- 最小堆(小顶堆):堆的每个父节点都小于其孩子节点;
堆的存储:
一般都用数组来表示堆,i结点的父结点下标就为
。它的左右子结点下标分别为
和
。堆排序:
由上面的介绍我们可以看出堆的第一个元素要么是最大值(大顶堆),要么是最小值(小顶堆),这样在排序的时候(假设共n个节点),直接将第一个元素和最后一个元素进行交换,然后从第一个元素开始进行向下调整至第n-1个元素。所以,如果需要升序,就建一个大堆,需要降序,就建一个小堆。
堆排序的步骤分为三步:- 建堆(升序建大堆,降序建小堆);
- 交换数据;
- 向下调整。
void AdjustDown(int arr[], int i, int n) { int j = i * 2 + 1;//子节点 while (j<n) { if (j+1<n && arr[j] > arr[j + 1])//子节点中找较小的 { j++; } if (arr[i] < arr[j]) { break; } swap(arr[i],arr[j]); i = j; j = i * 2 + 1; } } void MakeHeap(int arr[], int n)//建堆 { int i = 0; for (i = n / 2 - 1; i >= 0; i--)//((n-1)*2)+1 =n/2-1 { AdjustDown(arr, i, n); } } void HeapSort(int arr[],int len) { int i = 0; MakeHeap(arr, len); for (i = len - 1; i >= 0; i--) { swap(arr[i], arr[0]); AdjustDown(arr, 0, i); } }
STL 优先队列
一、相关定义
优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序,可以重载
<
操作符来重新定义比较规则。优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue,因为list的迭代器不是任意存取iterator,而pop中用到堆排序时是要求
randomaccess iterator
的!):priority_queue<vector<int>, less<int> > pq1; // 使用递增less<int>函数对象排序 priority_queue<deque<int>, greater<int> > pq2; // 使用递减greater<int>函数对象排序
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。
二、priority_queue
基本操作:
-
empty()
如果队列为空,则返回真 -
pop()
删除对顶元素,删除第一个元素 -
push()
加入一个元素 -
size()
返回优先队列中拥有的元素个数 -
top()
返回优先队列对顶元素,返回优先队列中有最高优先级的元素
在默认的优先队列中,优先级高的先出队。在默认的int型中先出队的为较大的数。
头文件:
#include <queue>
声明方式:
1、普通方法:
priority_queue<int> q; //通过操作,按照元素从大到小的顺序出队 priority_queue<int,vector<int>, greater<int> > q; //通过操作,按照元素从小到大的顺序出队
2、自定义优先级:
struct cmp { operator bool ()(int x, int y) { return x > y; // x小的优先级高 //也可以写成其他方式,如: //return p[x] > p[y];表示p[i]小的优先级高 } }; priority_queue<int, vector<int>, cmp> q; //定义方法 //其中,第二个参数为容器类型。第三个参数为比较函数。
3、结构体声明方式:
struct node { int x, y; friend bool operator < (node a, node b) { return a.x > b.x; //结构体中,x小的优先级高 } }; priority_queue<node>q; //定义方法 //在该结构中,y为值, x为优先级。 //通过自定义operator<操作符来比较元素中的优先级。 //在重载”<”时,最好不要重载”>”,可能会发生编译错误
优先队列 priority_queue
说明
优先队列是一种功能强大的队列,可以自动排序
头文件 & 声明
#include<queue>
一个优先队列的基本声明方式是
priority_queue<结构类型> 队列名;
e.g.
priority_queue<int> p; priority_queue<double> i;
常用的有:
priority_queue <node> q; //node是一个结构体 //结构体里重载了‘<’小于符号 priority_queue <int, vector<int>, greater<int> > q; //不需要#include<vector>头文件 //注意后面两个“>”不要写在一起,“>>”是右移运算符 priority_queue <int, vector<int>, less<int> >q;
基本操作
与队列一样
q.size();//返回q里元素个数 q.empty();//返回q是否为空,空则返回1,否则返回0 q.push(k);//在q的末尾插入k q.pop();//删掉q的第一个元素 q.top();//返回q的第一个元素 q.back();//返回q的末尾元素
特性
自动排序
默认的优先队列(结构体,重载小于)
#include<cstdio> #include<queue> using namespace std; priority_queue <int> q; int main() { q.push(10),q.push(8),q.push(12),q.push(14),q.push(6); while(!q.empty()) printf("%d ",q.top()),q.pop(); }
程序大意就是在这个优先队列里依次插入10、8、12、14、6,再输出。
结果是什么呢?14 12 10 8 6
也就是说,它是按从大到小排序的!
less 和 greater 优先队列
声明
priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q;
验证程序
#include<cstdio> #include<queue> using namespace std; priority_queue <int,vector<int>,less<int> > p; priority_queue <int,vector<int>,greater<int> > q; int a[5]={10,12,14,6,8}; int main() { for(int i=0;i<5;i++) p.push(a[i]),q.push(a[i]); printf("less<int>:") while(!p.empty()) printf("%d ",p.top()),p.pop(); pritntf("\ngreater<int>:") while(!q.empty()) printf("%d ",q.top()),q.pop(); }
结果
less<int>:14 12 10 8 6 greater<int>:6 8 10 12 14
可以看出,less是从大到小排序,greater是从小到大排序