长度为 100万 的序列，从中随机抽取 25万 个数据。

长度为 100万 的序列，从中随机抽取 25万 个数据。

算法：
1、先在 0-s 里随机取一数 [R];
2、将 [R] = [0], [0]将不再使用
3、先在 1-s 里随机取一数 [R1];
... 


并列出随机数取了三次以上的数据

	/**
	 * 长度为 s 的序列，从中随机抽取 n 个数据。
	 * 算法：
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * @param s
	 * @param n
	 * @return
	 */
	private static int[] getRandom(int s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须：s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须：s>=n ");
		}
		
		int[] data = new int[n];
		int[] temp = new int[s];
		for(int i=0; i<s; i++)
		{
			temp[i] = i;
		}
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			int idx = random.nextInt(s-i)+i;
			data[i] = temp[idx];
			temp[idx] = temp[i];
		}
		
		return data;
	}
	
	private static void print(int[] data)
	{
		for(int i=0; i<data.length; i++)
		{
			System.out.println(data[i]);
		}
	}
	
	/**
	 * 长度为 s 的序列，从中随机抽取 n 个数据。
	 * 算法：
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * 
	 * 并列出随机数取了三次以上的数据
	 * @param s
	 * @param n
	 * @return
	 */
	private static int[] getRandom02(int s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须：s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须：s>=n ");
		}
		
		int[] data = new int[n];
		int[] temp = new int[s];
		int[] selectCount = new int[s]; 
		for(int i=0; i<s; i++)
		{
			temp[i] = i;
			selectCount[i] = 0;
		}
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			int idx = random.nextInt(s-i)+i;
			data[i] = temp[idx];
			selectCount[idx]++;
			if(selectCount[idx]>3) //并列出随机数取了三次以上的数据
			{
				System.out.println(selectCount[idx] + ":" + idx);
			}
			temp[idx] = temp[i];
		}
		
		return data;
	}
	
	public static void main(String[] args)
	{
		
		//Collections.shuffle(null);
		
		getRandom02(1000000, 250000);
	}