google面试题（一）

有一个random number generator，是生成真实的随机数，而不是伪随机数，这个东西会生成几千亿个32位整数，打印出现次数前100的整数。

方法一：由于数的范围已经确定，采用计数排序的方法计算出0-2^31-1间数的出现次数，如下代码所示:
int[] array=new int[2^31-1]；
for i=0 to n-1 do {
  array[a[i]]++；
}
时间复杂度0(n),空间复杂度0(n)

接着问题就变成寻找数组array中前100大的数，可以采用类似快速排序的方式，先找第100大的数e的位置l，然后使用快速排序的partion方法重构数组，使得l前面的数都小于e，l后面的数都大于e，如下：
int radomize_select(int[] array, p, r, int i) { // 找第i大的数的位置
  if(p==r){ // 递归出口
    return array[p];
  }
  q=radomize_partion(A,p,r);
  k<-q-p+1;
  if(i<=k){
    return radomize_select(array,p,q,i);
  }
  else{
    return radomize_select(array,p,q,i-k);
  }
}
时间复杂度0(n),空间复杂度0(1)

void getResult(){
  int l=radomize_select(array, 0, n-1, 100);
  q=partion(l); //快速排序的partion
  for i=q to n-1 {
    输出 array[i];
  }
}
时间复杂度0(n),空间复杂度0(1)

综上，时间复杂度0(n),空间复杂度0(n)

方法二：采用哈希表, key is i, value is the count of i
Hashtable table=new Hashtable();
for i=0 to 2^31-1 do {
  int count=0;
  if(table.get(i)==null){
    count++;
  }
  else{
    count=++(table.get(i));
  }
  table.put(i,count);
}
剩下的方法和上面一样，略
时间复杂度0(n),空间复杂度>0(n)

对比以上2种方法，时间复杂度一样，但方法一的孔间复杂度稍微小于方法二，哈希表的空间一般情况下比普通的数组的空间要大