北京中软笔试题和面试题答案(最新)(二)

新高考网

  以下是我的第二种写法,用空间换了点时间,用C++语言写的:

  1. include

  1. include

  using namespace std;

  class Rand4{

  private:

  int a[10];

  int getNum(int index){

  while(a[index]==-1){

  ++index;

  index %= 10;

  }

  int ret = a[index];

  a[index] = -1;

  return ret;

  };

  void init(){

  for(int i=0;i<10;++i){

  a[i] = i;

  }

  };

  public:

  int Next(){

  init();

  int ret = (rand()%10) *1000;

  int index = 100;

  int time = 3;

  while(time>0){

  ret += getNum((rand()%10))*index;

  index /= 10;

  --time;

  }

  return ret;

  };

  };

  int main(int argc, char *argv[])

  {

  Rand4 r4;

  cout<

  cout<

  cout<

  system("PAUSE");

  return 0;

  }

  此法的时间复杂度为正宗的O(n),空间开销(不包含调用库函数的)就比前一个例子多了些.

  此法在n取m的随机计算中,m从0一直到趋近于n, 效率都是不变的.

  其他的高效方法暂时还没有想出.

中国点击率最高的一篇文章 !