面试题：随机数生成器

gistfile1.txt

package interview;

import java.util.Map;
import java.util.Random;
import java.util.concurrent.ConcurrentHashMap;

import static java.util.Optional.ofNullable;

/**
 * <pre>
 * 面试题：现有一随机数生成器 生成0的概率p 生成1的概率1-p
 * 利用该随机数生成器构造一个新的随机数生成器 可以均匀的生成 1~N之间的数
 *
 * 解题思路
 *
 * 假设 N=3
 *
 * 利用已有的随机数生成生成器 连续生成3次随机数 有如下的结果
 *
 * 0 0 0
 * 0 0 1
 * 0 1 0
 * 0 1 1
 * 1 0 0
 * 1 0 1
 * 1 1 0
 * 1 1 1
 *
 * 其中只有一个1的情况有 (概率均为 p * p * 1-p)
 * 0 0 1 ==> 3
 * 0 1 0 ==> 2
 * 1 0 0 ==> 1

 * 其中只有一个0的情况有 (概率均为  p * 1-p * 1-p)
 * 0 1 1 ==> 1
 * 1 0 1 ==> 2
 * 1 1 0 ==> 3

 *
 * 生成的3个随机数 若只有1个0或1 那么即返回其所在的索引 加一
 * 生成的3个随机数 若不满足条件 则重新生成
 *
 *
 *
 * </pre>
 * Created by zhuguowei on 5/6/17.
 */
public class RandomNumberGenerator {
    private static final Random random = new Random();

    /**
     * 生成0的概率 p
     * 生成1的概率 1-p
     *
     * @param zeroProbability 生成0的概率 百分数
     */
    public static int randomZeroAndOne(final int zeroProbability) {
        int rand = random.nextInt(100);
        if (rand < zeroProbability) {
            return 0;
        } else {
            return 1;
        }
    }

    /**
     * （平均）随机生成1~n之间的数
     *
     * @param zeroProbability
     * @param n               n>2
     * @return
     */
    public static int random(final int zeroProbability, final int n) {
        if (n < 2) {
            throw new IllegalArgumentException("n must great equal than 2");
        }
        /**
         *  1. 随机生成n个0或1
         *  2. 如果只有一个1或者0 那么就直接返回0或1所在的索引+1
         */
        Map<Integer, Integer> map = new ConcurrentHashMap<>(2);
        int[] index = new int[2];
        while (true) {
            for (int i = 0; i < n; i++) {
                int rand = randomZeroAndOne(zeroProbability);
                map.compute(rand, (k, v) -> v == null ? 1 : v + 1);

                index[rand] = i;
            }
            if (ofNullable(map.get(0)).orElse(0) == 1 || ofNullable(map.get(1)).orElse(0) == 1) {
                break;
            }
            map.clear();
        }
        return map.get(0) == 1 ? index[0] + 1 : index[1] + 1;
    }


}