北京中软笔试题和面试题答案（最新）(二)
以下是我的第二种写法,用空间换了点时间,用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, 效率都是不变的.
其他的高效方法暂时还没有想出.