明朝凌濛初写过初刻拍案惊奇，二科拍案惊奇，书中描写了很多离奇曲折的故事。而算法求解中，往往也会遇到让人拍案惊奇的方法，更有山穷水复疑无路，柳暗花明又一村。姑且用这篇文章，收集那些曾经遇到的那些虽然短小精悍，却拥有惊人解法的算法问题好了。
其中的大部分都是在bbs(水木清华 兵马俑 饮水思源 小百合)上讨论时碰到的，这些解法有些是别人提出的，有些则是我偶然间想到的。
1.大数据量寻找中文数及k位数
一般的方法可以采用k-th select 算法,但是如果元素数目太多时，无法一次读入内存，就带来了内存与磁盘交换。如果数的种类有限，比如全是整数int。那这个存在一个很优美的算法，大大简化了磁盘的读写。
(水源：xreborner)：
一个整数假设是32位无符号数
第一次扫描把0~2^32-1分成2^16个区间，记录每个区间的整数数目
找出中位数具体所在区间65536*i~65536*(i+1)-1
第二次扫描则可找出具体中位数数值
2.维护一个动态集合的中位数
(bmy：me)：采用两个堆
3.求前k大元素
(bmy：noname)：用最小堆方法减少磁盘读写
4.n个数,1–100000,从里面挖两个出来,其余的存在一个99998数组里面,要求把那两个找出来.除了用两数和,两数平方和来解方程,还有其他办法没，最好是O(n)时间,O(1)空间,不能改数组里的数。
(水源：xreborner)：
我先说用加法的方法吧
先扫描一遍求和，算出缺的两个数a、b的和为n
假设a<b，那么a<n/2,b>n/2
所以所有数就分成了两组，每组各缺一个数
然后再扫描一遍，两组分别求和找出各自缺的数
异或也是类似的原理，不过不会溢出
如果是少3个数？4个数呢….
5.如果数组中存在这样的数，这个数比它左边的所有的数大，并且比它右边的所有的数小，返回它的索引；如果不存在，返回-1。
例如：int[] arr = {5,3,6,2,7,10,8,12}; 7比它左边的数都大，比它右边的数都小，所以返回4。
1(smth：Roba269)：
线性，从左往右扫一遍，如果某元素是从左边到当前的最大，做个标记；从右往左扫一遍，如果某元素是从右边到当前的最小，做个标记。被标记两次的就是要找的元素。
2(smth：Andor)：
/* :证明 by phylips
实际上有个循环不变性，sol在每次循环中维护的是arr[0…i]之间的子数组满足条件
的那个最左边的位置 ，每次循环都保证了这个不变性
初始化a[0]只有一个元素，所以sol=0；
接下来假设sol是arr[0…i]中满足条件最靠左的那个位置 ，看arr[0…i+1]怎么维持
这个不变性。如果sol = -1,说明arr[0…i]不存在这种位置，加上arr[i+1],不会使原
来的arr[0…i]重新满足那个条件，如果arr[i+1]>left_max,显然它就是满足条件的最
左位置
如果sol != -1,分两种情况
arr[sol] >= arr[i+1]:
首先sol i+1这两个位置都不满足条件了，其次arr[sol+1]-arr[i]之间的arr元素也
不满足了，因为sol原来是arr[0…i] 中满足条件的位置，
也就是说arr[sol+1]-arr[i] 这些元素都大于arr[sol],也就更大于arr[i+1],这样
arr[sol+1]-arr[i]这些值的右边都有个小于它们的值arr[i+1],所以这些值都不可能满
足
所以应该sol = -1;
arr[sol] < arr[i+1]:
这个比较明显，arr[0.i+1]中满足条件的最左位置仍然是sol ，所以sol维持原状，
*/
#include <iostream>
using namespace std;
int main(){
int arr[] ={1,2,6,2,7,10,8,12};
int n = 8;
int sol = 0;
int left_max = arr[0];
for(int i = 0 ; i < n ; i++) {
if (sol == -1){
if(arr[i] > left_max)
sol = i;
}
else if (arr[sol] >= arr[i]){
sol = -1;
}
if(left_max > arr[i]){
left_max = arr[i];
}
}
cout << sol << endl;
while(true);
}
6.已知：A1 A2 A3 A4 … An
B1 = A2*A3* …*An
B2 = A1*A3* …*An
Bn-1 = A1*…*An-2*An
Bn = A1*A2*…*An-1
求出各个Bi（i= 1,2 …,n)
要求不能用除法（除法效率太低），时间负责度为nlog(n),。
(bmy：phylips)：
一个O(n)的算法：
先从上往下
B[1] = 1
for(i = 2 ; i <= n ; i++)
B[i] = B[i-1] * A[i-1];
然后从下往上
t = A[n];
for(i = n-1 ; i >= 1 ; i–){
B[i] = B[i] * t;
t *= A[i];
}
7.一个数组，其中只有一个数只出现一次，其余数皆出现偶数次。设计Time: O(n) Space: O(1)的算法，得出那个只出现一次的数。
(:noname)：异或
如果有两个数只出现一次呢？
(bmy：nemok提供)
1. 异或全体数，得到结果x0 ^ x1. Time: O(n)
2. 由于x0 != x1，故x0, x1至少有一位不相同，亦即至少可以从x0 ^ x1中找出某一位为"1"，记为该位第k位，且不妨设x0第k
位为"0"，x1第k位为"1". Time: O(1)
3. 异或全体第k位为"1"（或"0"）的数，结果即为x1（或x0）. Time: O(n)
4. 再将其与第1步结果异或，即得到另一个数. Time: O(1)
转载请注明作者：phylips@bmy 出处：http://duanple.blog.163.com/blog/static/7097176720094278566253/