在很久很久以前,我写了 《专注都难不倒 (5)》,之后就忘了再写下去了。直至昨晚有个师弟问我 4SUM 这道题的解法,我才恍然大悟:原来我经常写 “欲知后事,且听下回分解” 这类的蠢话。而且很无可避免的是,我老忘掉。
先把 4SUM 的解法贴出来吧,今天早上还特地去 Sicily 上优化了一下,可惜效果不太明显,只从 0.08s 提升到 0.03s 而已。
#define bits 40001 #define bits 40001 #define num 501 #define INFINITE 100000 #include<stdio.h> #include<stdlib.h> struct set_t { int number; //集合数目 int member[num]; //集合的元素 }m[4]; //4个集合 int sum1[bits]; int main() { int k,t,i,j; int max=0,min=0; for(i=0;i<4;i++) scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&m[i].number); for(i=0;i<4;i++) for(j=0;j<m[i].number;j++) scanf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d",&(m[i].member[j])); //输入集合 for(i=0;i<bits;i++) sum1[i]=INFINITE; //初始化sum1 for(i=0;i<m[0].number;i++) for(j=0;j<m[1].number;j++) { k=m[0].member[i]+m[1].member[j]+20000; //首先前两个集合相加,注意要将结果变换到[0, 40000] sum1[k]=m[0].member[i]; //并将结果储存在sum1中,注意sum1的数据结构 } for(i=0;i<m[2].number;i++) for(j=0;j<m[3].number;j++) //接着后两个集合相加 { k=m[2].member[i]+m[3].member[j]; t=20000-k; if(sum1[t]!=INFINITE) //如果相加的结果恰好等于sum1中已有结果的相反数,则输出 { printf("{5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d {5f7b659ff3b2818cd787bc9e2e970b98d3e4ece1905bf98c409dc266242d6105}d\n",sum1[t], t-sum1[t]-20000, m[2].member[i], m[3].member[j]); exit(0); //找到一个结果就可以退出了 } } } |
上面的程序还可以优化一下,譬如说前两个集合相乘,可以优化为最大数目的集合与最小数目的集合相差。(想想为什么?)
接下来是一道很常见的面试题目:从 N(N 很大,约为一千万) 个整数中找出最大的 M(M 约为 100) 个数
最直观的解法是:对 N 个数进行排序,输出最大的头 M 个数。如果用平均性能最好的快速排序的话,复杂度是 O(NlogN+M)。但是想想,有必要将全部数字排序吗?只需要排出 M 个数字就可以了吧。那么循环扫描 N 个数字,扫描 M 遍,每次找出最大的数字,这时候复杂度是 (N*M), 事实上比最直观的解法的效率还差。
那么,我们建立一个大小为 M 的数组吧。扫描 N 的时候,每碰到一个数字 a 就和数组 M 里面的最小值来比较,如果比这个最小值大的话,就用 a 来替代那个最小值,然后线性搜索数组 M 的最小值,准备好下一次判断。
这个算法依赖于初始数组 N 的数据。N 中的数据如果是非递增的话,O(N),不过如果 N 中的数据是非递减的话,那就很悲剧了,是 O(N*M)。上个算法中,搜索 M 用的是线性搜索,可不可以优化一下呢?答案是肯定的。
如果 M 中的数据是线性有序的话,那就可以用折半搜索了,不过插入数据的时候会很麻烦,需要移动很多的数据。
用链表可行么?尽管不用移动数据,可惜链表不支持用折半搜索。
只好用最小堆了,尽管写一个堆对我而言绝对不是一件容易的事情。具体的算法如下:
先将数组 N 中的头 M 个数据构建成最小堆,堆的大小为 M(那么其最小的值就在堆顶 N[0] 上了),然后从第 M+1 个数据开始扫描数组 N。如果该数据小于堆顶 N[0],移动到下一个数据。如果该数据大于堆顶 N[0],用其替换掉 N[0],并利用堆来将其 “沉” 下去,并将 M 中最小的元素 “浮” 上来。
算法的效率是 O(N*logM)。
代码从略。
嗯嗯嗯,我也不会。
不断的用新的元素去冲击堆顶
用堆吧,我喜欢
我也喜欢,可就是不怎么会写堆。
占个沙发慢慢看好文章..
看到堆恍然明白原来 sicily 1482 可以用 Sicily 1778 的方法写了. 原来一道题目要看出好的算法真的不是那么容易的. 比如说,Sicily 1001,一直没看出状态转移方程,搞了半天推了个变形的 fibonacci,结果代码实现起来有点复杂,今天才知道竟然可以 DP 之..
变形的 fibonacci?我还是不懂这样应当怎么做…
囧.. 一直以为评论被回复的话会收到邮件通知的.
刚刚回去看了下代码, 结果发现其实就是 fibonacci 用备忘录的方法, 其实也就是动态规划了.
呵呵,以前是会收到邮件通知的,现在好像服务器有些问题的样子,时令时不灵的