[QQ群: 189191838，对算法和C++感兴趣可以进来] 

第一个问题，查找出1000万数据中最大的100万条。

   对这个问题的第一反应就是利用排序算法，排序有很多种。其中以快排用的最多。只需多次paration得到前100万即可。

   还有一种思路就是建立一个100万大小的堆，然后再不断的对进来的数据进行堆调整。当查找出的数据越小的时候，优势会特别明显。比如100万变成100的时候，用堆将是最好选择。

第二个问题，对最大数为1000万的100万条数据进行排序，且数据无重复。

   这个其实也可以用堆排序，快速排序进行处理。但是还可以用位图的方式进行处理。位图的时间复杂度是N，快于他们，只不过需要开辟100万/8个字节而已。

   如果把题目改成，999999（100万-1）条数据中是由1-100万组成，且无重复，查找出那个缺失的数据。用位图的优势将会越加体现。比其他排序方法好很多。

第三个问题，100万+1条数据中都是两两重复的，只有一条是单着的。

   当然，我们可以用排序。但是用这些数据全部与&,会快很多。所以位操作有时候很重要。

第四个问题，查找一本书中是否存在某个单词。

   这个问题，可以有很多种查找方式，比如说排序，通过基排序的方式，然后二分查找，这个很好，但是感觉效率还是不是很高。

  或者用hash对书中所有单词进行hash，再比较。

  我认为最好的方式是建立字典树tire，这个很快很快。

第五个问题，随机产生1--N中M个数。

  如果可以产生重复的数，那么很简单，直接rand(N) m次即可。但是如果不可重复呢？

  1，利用随机的思想，开一个N大的数组，然后for i=1...M;每次产生一个随机数k,如果k>i,交换数组中的数，否则不交换，重复M次。

  2，利用概率的思想，第一个数在M个数里面的概率是m/N,则随机产生一个数k，(1...N)如果k小于m,则添加到m里面，同时m=m-1,对第二个数2,进行处理，此时2添加到数组中的概率应该是(m)/N-1....后面同理

  本来不想粘贴代码，还是粘一下吧“

 1 public static void getM(int n,int m){//等概率的取出其中m个数 2         for(int i=0;i<n;i++){ 3             Random random=new Random(); 4             int k=random.nextInt(10000); 5              6             if(m>0&&k%(n-i)<m){ 7                 System.out.print(":"+i+" "); 8                 m--; 9                 if (m==0) {10                     break;11                 }12             }13         }14     }

View Code

第六个问题，对于两个字符串，如何得到其中相同的子串呢？(不是子序列)子序列可不连续，但是子串必须连续。

   第一反应用动态规划的思想求解。(暴力法时间复杂度太高)

   第二，可以通过建立后缀数组的方式求解，后缀数组，排序。比较，得到答案。复杂度要比动态规划好。只不过是空间换时间罢了。代码就不贴了。

第七个问题，一堆单词集合M，一个字符串S。求出S可以在M中找到多少个单词。比如M={good,thank, you,are,do},S="goodoayouk".能到找到的单词是good,do,you.三个。

   可以暴力法，硬匹配；

   一种比较好的方法应该是利用AC自动机搜索。这个挺好，快！

(本文只用作自己总结，故没有展开来说，相关细节可以搜索其他文章,排版也不是我的长项，所以大家将就吧。)

未完待续。。。

    版权所有，欢迎转载，但是转载请注明出处：潇一

简单总结下几个算法