这道是个概率题:
题目:
|
给你一组整数链表,链表长度不定,让你随机取里面的 N 个数据,链表长度大于 N,保证 N 个数被从链表中等概率获得,不能计算链表长度并且只能遍历链表一次
|
这题我一开始也没有思路，经过面试官的提醒，说可以用置换的方法来解，于是解答出了解法：把链表前 N 个数先放进数组，然后取每 N + 1 个数，然后取一个 N + 1 的随机数，如果小于 N，则在取出的 N 个数中换出去第(N + 1) % N个数。这样一个一个按此算法一直到链表结束。
实际我最后一步取模的方法不对，应该是随机换出去一个。
下面算算随机换出去是否是等概率的。选出的前N个数被选中概率都为 N，第 N + 1 个数被选中的概率是 N / (N + 1)，它把前面 N 个数换出去一个，每个数被换出去的概率是 1 / N，那么，前 N 个数留下的概率就为 1 - (1 / N) * (N / (N + 1)) = N / (N + 1)，然后取第 N + 2 个数，照此方法进行替换，直到链表最后一个数。具体概率我就不算了，肯定是想等的。
下面把代码贴出来，BASE类只是个日志类，可以在前面的博客中找到，这里就不贴了：
|
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Random;
/**
* <pre>
* 给你一个组整数,数据长度不定,让你随机取里面的数据,保证等概率,不能计算数据长度并且只能遍历链表一次
* </pre>
*
* @author chouy
*/
public class EquiprobableGetNumber extends Base
{
public static void main(String[] args)
{
int NUMBERCOUNT = 10;
Random random = new Random();
int max = random.nextInt(50);
info("length: " + max);
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 1; i < max; i++)
list.add(i);
info("init: " + list.toString());
int[] result = new EquiprobableGetNumber().calc(list, NUMBERCOUNT);
info("result: " + Arrays.toString(result));
}
public int[] calc(LinkedList<Integer> array, int resultLength)
{
Random random = new Random();
int[] result = new int[resultLength];
int i = 0;
for (; i < resultLength && !array.isEmpty(); i++)
result[i] = array.remove();
while(!array.isEmpty())
{
int tmp = array.remove();
int rdmInt = random.nextInt(i++);
if (rdmInt < resultLength)
{
result[random.nextInt(resultLength)] = tmp;
}
}
return result;
}
}
|
我的算法有错误或有其它的算法，请和我交流。
