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

　　以下是我的第二种写法,用空间换了点时间,用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, 效率都是不变的.

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