发个面试时的经典题目

Question

原贴:http://bbs.hadoopor.com/thread-138-1-1.html
现有1亿个整数均匀分布，如果要得到前1K个最大的数，求最优的算法。­
（先不考虑内存的限制，也不考虑读写外存，时间复杂度最少的算法即为最优算法）­
­
我先说下我的想法:分块，比如分1W块，每块1W个，然后分别找出每块最大值，从这最大的1W个值中找最大1K个，那么其他的9K个最大值所在的块即可扔掉，从剩下的最大的1K个值所在的块中找前1K个即可。那么原问题的规模就缩小到了1/10。­
­
问题：­
1.这种分块方法的最优时间复杂度。­
2.如何分块达到最优。比如也可分10W块，每块1000个数。则问题规模可降到原来1/100。但事实上复杂度并没降低。­
3.还有没更好更优的方法解决这个问题。­
­
希望大家来讨论讨论，踊跃提出自己的解决方式和思路。­

Answer 1

楼主你的想法可能会有漏掉的，拥有最大值的那块，前面1000个数未必就是最大的1000个数如果按分块来做，1W*1W块，需要在每一块都找到前1000个，然后对剩下的1000W个数继续分组找...

Answer 2

分组没错的。就要看所谓的均匀怎么算了。如果不能有明确的定义，每组还是必须取1000个。如果有明确定义的话，就好办多了。题外话：如果1亿个数是连续或有规律的话，更好办了，开一个boolean[] b = new boolean[100,000,000]

Answer 3

TreeSet<Integer> set = new TreeSet<Integer>();
List<Integer> lst = new ArrayList<Integer>();
int numberCount = 1000000000;
int maxNumber = numberCount;
Random random = new Random();
for (int i = 0; i < numberCount; i++) {
int randomInt = random.nextInt(maxNumber);
Integer inte = new Integer(randomInt);
if (set.contains(inte))
{
lst.add(inte);
}
if (set.size() < 1000)
{
set.add(inte);
}
else
{
if (set.first().intValue() < randomInt)
{
set.remove(set.first());
set.add(randomInt);
}
}
}Iterator iterator = set.iterator();
while(iterator.hasNext()) {
lst.add((Integer)iterator.next());
}Collections.sort(lst);
for (int i = 0; i < 1000; i++)
{
System.out.println(i + ":" + lst.get(lst.size() - i - 1));
}套个main就可以跑了，耗时大概在100S左右，每1KW用时不到2S。

Answer 4

编程之美上的寻找N个数中最大的前K数，给出了一种算法，我认为比较好：
假设N个数存储在数组S中，我们从数组S中随机选出一个元素X，把数组分为两部分Sa和Sb.Sa中的元素都大于X，Sb中的元素都小于X：
这是，有两种可能性：
1.Sa中元素的个数小于K，Sa中所有的数和Sb中最大的K-|Sa|个数（|Sa|指Sa中元素的个数）就是数组S中最大的K个数。
2.Sa中元素的个数大于或等于Ｋ，则直接返回Sa中最大的K个元素。
平均时间复杂度O(N*log2 K)
伪代码：Kbig(S,K)
   if(k<=0):
      return []
   if(length S<=K):
      return S
   (Sa,Sb)=Partition(s)
   return Kbig(Sa,k).Append(Kbig(Sb,k-length Sa)
//////////////////////////////////////////////////
Partition(S):
    Sa=[];
    Sb=[];
    Swap(s[1],S[random()%length S])
    p=S[1]
    for i in [2:length S]:
        s[i] > p ? Sa.Append(s[i]):Sb.Append(S[i])length Sa<length Sb ? Sa.Append(p):Sb.Append(p)
return (Sa,Sb)
我的代码：#include <stdio.h>   
#include <tchar.h>   
#include <iostream>   
#include <vector>   
#include <stdlib.h>   
#include <time.h>   
using namespace std;   
vector<int> Kbig(vector<int>&,int);   
pair<vector<int>,vector<int> > Partition(vector<int>);   
int main()   
{   
    vector<int> origin(10000,0);   
    int k;   
    cout <<"origin array:"<<endl;   
    for (int i = 0;i < 10000;i++)   
    {   
        origin[i] = rand() % 10001;   
        cout << origin[i] << " ";   
    }   
    cout << endl;   
       
    cout << "请输入你想找的最大的数的个数："<<endl;   
    cin >> k;   
    origin = Kbig(origin,k);   
  
    cout << "最大的" << k << "个数是："<< endl;   
    for(vector<int>::iterator iter = origin.begin();iter != origin.end(); ++iter )   
        cout << *iter <<" ";   
    cout << endl;   
       
    return 0;   
}   
  
vector<int> Kbig(vector<int>& origin,int k)   
{   
    pair<vector<int>,vector<int> > ret;   
    vector<int> sa,sb,temp;   
    if(k <= 0)   
        return origin;   
    if(origin.size() <= k)   
        return origin;   
    ret = Partition(origin);   
    sa = ret.first;   
    sb = ret.second;   
    if (sa.size() >= k)   
    {   
        return Kbig(sa,k);   
    }   
    else  
    {   
        temp = Kbig(sb,k - sa.size());   
        for (vector<int>::iterator iter = temp.begin(); iter != temp.end();++ iter)   
        {   
            sa.push_back(*iter);   
        }   
        return sa;   
    }   
       
}   
  
pair<vector<int>,vector<int> > Partition(vector<int> origin)   
{   
    srand((unsigned)time(NULL));   
    vector<int> sa,sb;   
    pair<vector<int>,vector<int> > ret;   
    int p;   
    swap(origin[0],origin[rand()%origin.size()]);   
    p = origin[0];   
    for (vector<int>::iterator iter = origin.begin() + 1;iter != origin.end();++iter)   
        *iter > p ? sa.push_back(*iter) : sb.push_back(*iter);   
    sa.size() < sb.size() ? sa.push_back(p) : sb.push_back(p);   
    ret = make_pair(sa,sb);   
    return ret;   
}  

Answer 5

有一个非分布式计算的方法，时间效率也低。
位图算法。
楼主不妨可以看一看。题目给的条件是一亿个（10000*10000）整数均匀分布，那么这1Y个整数按照题目所述，应该有重复、漏掉（即不可能是从1~1Y）。
那么我现在给的一个算法是：1、定义二维数组 int Numbers[10000][10000]
2、初始化 Numbers[i][j]=0  (0<=i,j<10000)
3、遍历所给的1Y个数据，数据 CurrentNumber则应该放置在 Numbers[CurrentNumber/1000][CurrentNumber%1000],即Numbers[CurrentNumber/1000][CurrentNumber%1000]++Tips：
    （1）上面Numbers[CurrentNumber/1000][CurrentNumber%1000]++是针对不可漏掉重复数据，比如9999999 有五个，那么它如果在前1K内，应该会占五个名额...4、最后一步开始从Numbers[9999][9999]开始输出前1K个数据
    当Numbers[i][j]==0时不计算在内
    党Numbers[i][j]!=0时，按照Numbers个数输出 i*10000+j （i*10000+j这个才是真正的数）
    知道总计1K个数据输出完毕。我测试过，用C语言实现这样的算法，遍历完1Y个数据并输出前1K个，耗时不会太长，可以在几秒内。
如果用hadoop和mapreduce分块的话，其分块的过程就要耗费好多资源的。
over如果上述内容能给你一点点启发，不胜荣幸。