算法与acm

算法之拍案惊奇

2009年5月27日 阅读(341)

明朝凌濛初写过初刻拍案惊奇,二科拍案惊奇,书中描写了很多离奇曲折的故事。而算法求解中,往往也会遇到让人拍案惊奇的方法,更有山穷水复疑无路,柳暗花明又一村。姑且用这篇文章,收集那些曾经遇到的那些虽然短小精悍,却拥有惊人解法的算法问题好了。

其中的大部分都是在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/
 

You Might Also Like