利用stl中nth_element()找出第k小的数字

找出一个数组中第k小的数 一、朴素做法 sort() 时间复杂度：O(nlogn) 二、利用STL库函数nth_element() 时间复杂度：O(n) 用法：`nth_element(a,a+k,a+n)` 长度为n的数组a[]中找出第k小的数

rand()（随机化算法）

1.rand() 函数的基本用法 rand() 函数不需要参数，它会返回一个从 0 到最大随机数之间的任意整数。 最大随机数的大小通常是固定的一个大整数，例如 RAND_MAX。 ***注意：***在windows操作系统下最大为2^15-1（即32767），LINUX坏境下最大为2^31-1 如要生成更大范围随机数需要`rand()*rand()`或`(rand()

RMQ算法（计算机求区间最值算法）

一、求区间最大值的各种方法及时间复杂度 1、朴素（即搜索），O(n)-O(qn) online。 2、线段树，O(n)-O(qlogn) online。 3、ST（实质是动态规划），O(nlogn)-O(q) online。 ST算法（Sparse Table），以求最大值为例，设d[i,j]表示[i,i+2^j-1]这个区间内的最大值，那么在询问到[a,b]区间的最大值时答案就是m...

gcd和lcm

gcd：最大公约数 lcm：最小公倍数 **2个数a,b的gcd、lcm：** GCD2=__gcd(a,b) LCM2=a*b/GCD **3个数a,b,c的gcd、lcm：** GCD3=__gcd(GCD2,c) LCM3=LCM2*c/GCD3 代码实现： ``` #include using namespace std; // 求最大公约数 ...