百亿人口，选八十万移民的解法。

地球人口越来越多，终于达到了100亿了。还好，发现了一颗适合人类居住的星球。现在，需要派遣八十万个人先期进驻。如何选出这八十万的人呢？

算法描述：
1、有六个数 0 1 2 3 4 5，随机数为 4 2 2 1 0 0。
2、第一次从六个数里取随机数，为4，则将第4个数取出，变为0123*5，取出的数为 4
3、而后，将第5个数交换到第4个数的位置上，即数字变为 01235
4、第二次从五个数里取随机数，为2，则将第2个数取出，变为01*35，取出的数为 2
5、而后，将第4个数交换到第2个数的位置上，即数字变为 0153
6、第三次从四个数里取随机数，为2，则将第2个数取出，变为01*3，取出的数为 5
7、而后，将第3个数交换到第2个数的位置上，即数字变为 013
8、第四次从三个数里取随机数，为1，则将第1个数取出，变为0*3，取出的数为 1
9、而后，将第2个数交换到第1个数的位置上，即数字变为 03
10、第五次从两个数里取随机数，为0，则将第0个数取出，变为*3，取出的数为 0
11、而后，将第1个数交换到第0个数的位置上，即数字变为 3
12、第六次随机数为0，则将第0个数取出，变为*，取出的数为 3

即，取到的数为 425103。

另外，代码有错误，已更改。

package test;

import java.util.Hashtable;
import java.util.Random;
import java.util.Vector;

public class DaLuan {

	/**
	 * 长度为 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]>1) //并列出随机数取了三次以上的数据
			{
				System.out.println(selectCount[idx] + ":" + idx);
			}
			temp[idx] = temp[i];
		}
		
		return data;
	}
	
	/**
	 * 这个版本针对的是从百亿级数据里取数据的。
	 * 
	 * 长度为 s 的序列，从中随机抽取 n 个数据。
	 * 算法：
	 * 1、先在 0-s 里随机取一数 [R];
	 * 2、将 [R] = [0], [0]将不再使用
	 * 3、先在 1-s 里随机取一数 [R1];
	 * ...  
	 * @param s
	 * @param n
	 * @return
	 */
	private static long[] getRandom03(long s, int n)
	{
		if(s<=0 || n<=0)
		{
			throw new RuntimeException("必须：s>0 且 n>0 ");
		}

		if(s<n)
		{
			throw new RuntimeException("必须：s>=n ");
		}
		
		long[] data = new long[n];
		Hashtable<Long, Long> ht = new Hashtable<Long, Long>();
		
		Random random = new Random();
		random.setSeed(System.currentTimeMillis());
		
		for(int i=0; i<n; i++)
		{
			long l = random.nextLong();
			if(l<0)
			{
				l= Math.abs(l);
			}
			long idx = l % (s-i);
			
			if(ht.get(idx)==null)
			{
				data[i] = idx;
			}
			else
			{
				data[i] = ht.get(idx);
			}
			
			if(ht.get(s-i-1)==null)
			{
				ht.put(idx, s-i-1);
			}
			else
			{
				ht.put(idx, ht.get(s-i-1));
			}
		}
		return data;
	}	


	public static void main(String[] args)
	{
		System.out.println(Runtime.getRuntime().maxMemory());
		
		//Collections.shuffle(null);
		
		//print(getRandom02(3000000, 2500));
		//getRandom03(10000000000L, 1000000);
		getRandom03(10000000000L, 800000);
		//getRandom03(10000000000L, 1000000); //需要设置vm参数 -Xms64M -Xmx256M
	}
}

评论

3 楼 zwhc 2010-08-06  

fy616508150 写道

没看明白``题目的意思``

就是从百亿里，取八十万的数据。

题目的写法，只是为了增加趣味性而已。

2 楼 fy616508150 2010-08-06  

没看明白``题目的意思``

1 楼 zwhc 2010-08-06  

当然，还可以分段取。比如，将 100亿分成 80万个组，即每组 12500。从中选一个即可。

还可以象股票新股摇号那样。