zhangas

Pay more attention

0%

Posted on Edited on

lower_bound() 时间复杂度为O(n)

template <class ForwardIterator, class T>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val);

函数作用

在升序的情况下，返回指向第一个值不小于val的位置，即返回第一个大于等于val值的位置。（通过二分查找）
借助数组实现 从a[0]到a[n]

1
cout<<a[lower_bound(a,a+n,val)-a];

输出第一个大于或等于val的数

nth_element() 时间复杂度为O(n)

称第 n 个元素为升序序列中”第n大”的元素
例如

1
2 4 6 8 10

2为第1小 8为第4小

默认升序

1
2
3
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last);

自定义cmp排序

1
2
3
4
void nth_element (RandomAccessIterator first,
                  RandomAccessIterator nth,
                  RandomAccessIterator last，
                  Compare cmp);

函数作用

1
nth_element(a,a+n,a+k);//使第k小整数就位

Posted on Edited on

加法 A+B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector<int> add(vector<int> &a,vector<int> &b){//默认字符串a的长 
	vector<int>c;//加上引用不用拷贝整个数组 可以加快效率 
	if(a.size()<b.size()){
		return add(b,a);
	}
	int t=0;//处理进位问题 
	for(int i=0;i<a.size();i++){
		t+=a[i];
		if(i<b.size()){
			t+=b[i];
		}
		c.push_back(t%10);
		t/=10;
	}
	if(t){//若最高位向前进了1 则添加到c中
		c.push_back(t);
	}
	return c;
}

减法 A-B

需要判断读入A和B的大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//比较A和B的大小 
bool cmp(vector<int>&a,vector<int>&b){
	if(a.size()!=b.size()){
		return a.size()>b.size();
	}
	//长度相同 
	for(int i=a.size()-1;i>=0;i--){
		if(a[i]!=b[i]){
			return a[i]>b[i];
		}
	}
	return true;	
}
vector<int> subtraction(vector<int>&a,vector<int>&b){
	vector<int>c;//计算A-B 
	for(int i=0,t=0;i<a.size();i++){
		t=a[i]-t;
		if(i<b.size()){//判断b是不是已经越界了 
			t-=b[i];
		}
		c.push_back((t+10)%10);
		//等价于判断t<0时候 t+=10 t<10时 直接在尾部添加t
		t=t<0?1:0;//更新t 若借一 t在下次循环要减去一
	}
	while(c.size()>1&&c.back()==0){//例如123-120=3 容器c的长度和a一样 返回的应该是003
		c.pop_back();//删除容器尾部元素
	}
	return c;
	
}

乘法 A*b

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> multiple(vector<int>a,int b){
	vector<int>c;
	int t=0; 
	for(int i=0;i<a.size();i++){
		t+=a[i]*b;		
		c.push_back(t%10);
		t/=10;
	}
	if(t){//t不为零时 可以加到c的最高位上 
		c.push_back(t);
	}
	return c;
}

除法