北京中軟筆試題和面試題答案（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, 效率都是不變的.

　　其他的高效方法暫時還沒有想出.