編程珠璣之生成0至n-1之間的k個不同隨機序列的擴展問題 --2014人人網筆試題目

由這個問題我們引出以下這個筆試題目的問題：

“使用一個長度為n的數組來產生隨機數，當產生的隨機數與數組的存在的相同則重新隨機，當不同時插入到數組中，使用這種方法產生1到n的隨機數的期望次數是多少次？（編程實現）”

一般的思想是產生一個隨機數 arr[i] 後，和前麵已經產生的arr[0]~arr[i-1]進行比較，如果有重複的就重新產生一個，該算法的平均時間複雜度為：O（n^2) ，而最壞複雜度為無限！！

這裏我們按照編程珠璣上那個問題的擴展想法，利用空間換時間的算法，生成隨機排列的數，此時時間複雜度為O（n）。

（1）建立一個長度為n+1的臨時數組b，對該數組賦值依次賦值0~n, 即b[i] = i;

（2）取一個1~n之間的隨機整數k=rand(0,n]，取b[k]讀入arr[i]，再將b數組最後一個元素b[b.size-1]賦值給b[k]，將b的長度減1；

代碼實現：

/*
*BLOG:https://blog.csdn.net/wdzxl198
*AUTHOR:Atlas
*EMAIL:wdzxl198@163.com
*/
#include<iostream>
using namespace std;

void Random(int *arr,int length)
{
	srand(time(NULL));
	int i,randnum;
	int limitsize = length;
	int b[limitsize];
	for(i=0; i<limitsize; i++)
	{
	   b[i] = i+1;
	}
	for(i=0; i<length; i++)
	{
	   randnum = rand()%limitsize;
	   limitsize--;
	   arr[i] = b[randnum];
	   b[randnum] = b[limitsize];
	}
}

int main()
{
	int arr[100];
	//假使隨機出1到100的隨機數
	Random(arr,100);	
	for(int i=0;i<100;i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;	
	
	quickSort(arr,0,99);

	for(int i=0;i<100;i++)
	{
		cout<<arr[i]<<" ";
	}
	
	cout<<endl;	
	system("PAUSE");
	return 0;
} 

這種方法的是O（n）時間複雜度，但是沒有求出題目中期望的次數。

在求期望的過程中，我發現一篇博文，題目是有一個數組，每次從中間隨機取一個，然後放回去，當所有的元素都被取過，返回總共的取的次數。寫一個函數實現。複雜度是什麼。，這個題目與文章中的類似，轉載過來分析下，

import java.util.Random;  
import java.util.Set;  
import java.util.TreeSet;  
/** 
 * #麵試題#有一個數組，每次從中間隨機取一個，然後放回去，當所有的元素都被取過，返回總共的取的次數。 
 * 寫一個函數實現。複雜度是什麼。 
 * bitmap，隻要一個bit就可以標記是否被取過，可參考《編程珠璣》的位圖排序 
 *  
 * 時間複雜度的話，我不太會算，以下是引用https://github.com/vyan/test/blob/master/accessTimes.cpp： 
 * 使用bit打點記錄已經取的數，  
 * 複雜度分析，假設數組總長度為n  
 * 取到第1個之前未被取到的數的期望 E(1)=1  
 * 取到第2個之前未被取到的數的期望 E(2)=n/n-1  
 * 取到第3個之前未被取到的數的期望 E(3)=n/n-2  
 * ... 
 * 取到第n個之前未被取到的數的期望 E(n)=n/1  
 * 總得期望次數E=n+n/(n-1)+n/(n-2)+...+n/1; 
 *              =n(1+1/(n-1)+1/(n-2)+...+1/1)  
 *              =nln(n)  
 * 所以算法平均複雜度為nlogn  
 *  
 * 下麵的代碼裏麵，除法和求模運算我都用位運算來實現，事實上直接用java提供的（/,%）也可以 
 * 同時，為了驗證是否真的取到了數組的所有元素，我用了TreeSet保存已選中的下標（去重） 
 *  
 * 最後，還有一個問題是，可能取了很多次，都沒能全選中，這個時候可以設置一個最長時間或者最大嚐試次數，超過則結束程序， 
 * 避免程序長時間運行甚至死循環 
 *  
 * @author lijinnan 
 *  
 */  
public class TimesOfAccessArray {  
  
    public static final int SHIFT = 5;  
    public static final int BLOCK_SIZE = (1 << SHIFT);  //32  
    public static final int MASK = (1 << SHIFT) - 1;  //31  
  
    public static void main(String[] args) {  
        int[] array = new int[200];  
        long times = accessTimes(array);  
        System.out.println(times);  
    }  
      
    public static long accessTimes(int[] array) {  
        if (array == null || array.length == 0) {  
            return -1L;  
        }  
        long result = 0L;  
        int len = array.length;  
        int[] bitmap = new int[divide(len, BLOCK_SIZE) + 1];  
        int setTimes = 0;  
        Set<Integer> set = new TreeSet<Integer>();  
        while (setTimes < len) {  
            int pos = new Random().nextInt(len);  
            set.add(pos);  
            if (set(bitmap, pos)) {  
                setTimes++;  
            }  
            result++;  
        }  
        System.out.println(set);  
        return result;  
    }  
      
    public static boolean set(int[] bitmap, int pos) {  
        boolean result = false;  
        int blockNo = divide(pos, BLOCK_SIZE);  
        int index = mod(pos, BLOCK_SIZE);  
        boolean notExist = (bitmap[blockNo] & (1 << index))== 0;  
        if (notExist) {  
            bitmap[blockNo] |= (1 << index);  
            result = true;  
        }  
        return result;  
    }  
  
    public static boolean exist(int[] bitmap, int pos) {  
        int blockNo = divide(pos, BLOCK_SIZE);  
        int index = mod(pos, BLOCK_SIZE);  
        return (bitmap[blockNo] & (1 << index)) != 0;  
    }  
      
    private static int divide(int x, int y) {  
        return x >> offSet(y);  
    }  
  
    private static int mod(int x, int y) {  
        int z = x;  
        int i = offSet(y);  
        return z - ((z >> i) << i);  
    }  
      
    //e.g. 32=2^5, return 5 隻考慮2的冪  
    private static int offSet(int y) {  
        return howManyBits(y) - 1;  
    }  
  
    //二進製的表示裏麵，有多少位。例如32是6位  
    private static int howManyBits(int y) {  
        int bitNum = 0;  
        while (y != 0) {  
            y = (y >> 1);  
            bitNum++;  
        }  
        return bitNum;  
    }  
     
  
}