【每日算法Day 50】随机

简单的伪随机数可以使用Math.random()，要更精确地使用伪随机数可以创建java.util.Random类的对象。蓄水池随机抽样法是不确定符合条件的元素的数量时就要做选择、同时要保证最终所有元素被选择的概率相同时的好思路。

java.util.Random类简要介绍

Random类中实现的随机算法是伪随机，也就是有规则的随机。在进行随机时，随机算法的起源数字称为种子数(seed)，在种子数的基础上进行一定的变换，从而产生需要的随机数字。

相同种子数的Random对象，相同次数生成的随机数字是完全相同的。也就是说，两个种子数相同的Random对象，第一次生成的随机数字完全相同，第二次生成的随机数字也完全相同。这点在生成多个随机数字时需要特别注意。

构造方法

public Random()
public Random(long seed)

第一个构造方法使用一个和当前系统时间对应的相对时间有关的数字作为种子数，然后使用这个种子数构造Random对象。

第二个构造方法可以通过制定一个种子数进行创建。

方法

boolean nextBoolean() //返回下一个伪随机数，它是取自此随机数生成器序列的均匀分布的boolean值。
void nextBytes(byte[] bytes) //生成随机字节并将其置于用户提供的 byte 数组中。
double nextDouble() //返回下一个伪随机数，它是取自此随机数生成器序列的、在0.0和1.0之间均匀分布的 double值。
float nextFloat() //返回下一个伪随机数，它是取自此随机数生成器序列的、在0.0和1.0之间均匀分布float值。
double nextGaussian()    //返回下一个伪随机数，它是取自此随机数生成器序列的、呈高斯（“正态”）分布的double值，其平均值是0.0标准差是1.0。 
int nextInt() //返回下一个伪随机数，它是此随机数生成器的序列中均匀分布的 int 值。 
int nextInt(int n) //返回一个伪随机数，它是取自此随机数生成器序列的、在（包括和指定值（不包括）之间均匀分布的int值。
long nextLong() //返回下一个伪随机数，它是取自此随机数生成器序列的均匀分布的 long 值。
void setSeed(long seed) //使用单个 long 种子设置此随机数生成器的种子。

LeetCode 384. 打乱数组 (opens new window)

题目描述

打乱一个没有重复元素的数组。

示例

// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();

// 重设数组到它的初始状态[1,2,3]。
solution.reset();

// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();

解题思路

关于重设功能，只需要保存一份原始数组的拷贝就可以了。关于洗牌功能，其实就相当于每次从可选的范围中选择一个数拿到依次结果数组中。再对剩余的数进行相同的操作。那么我们其实可以通过交换来划分结果。从左向右依次把可选择范围中的随机位置和边界头部元素交换，这样就实现了结果的扩大和待处理元素集的缩小。

public class No384_ShuffleAnArray {
    private int[] original;
    private int[] result;
    private Random rand = new Random();
    private final int n;

    public No384_ShuffleAnArray(int[] nums) {
        original = nums.clone();
        result = nums;
        n = nums.length;
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        result = original;
        original = original.clone();
        return result;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        result = original;
        original = original.clone();
        for (int i = 0; i < n; i++) {
            int randomBorder = rand.nextInt(n - i) + i;
            int temp=result[i];
            result[i] = result[randomBorder];
            result[randomBorder] = temp;
        }
        return result;
    }
}

LeetCode 398. 随机数索引 (opens new window)

题目描述

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。

注意： 数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。

示例

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);

// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);

解题思路

一开始可能想到的是先遍历一遍得到等于目标数的数字的个数N，然后再遍历一遍遇到相等的值时以1/n的概率返回其下标。但是这样不能保证一定能返回，有可能遍历完都不会返回。而正确的取值范围是离散的，该怎么使得伪随机函数等概率地在这些下标中取值呢？

有个蓄水池抽样问题，能在不断丢弃与抽样的过程中保持每份元素最终被抽样的概率相同。其原理大致为：如果要从1个数中随机抽取1个数，则抽取时概率为1；如果在此基础上新增一个数，如果要保证抽取1个数这两个数的概率都为1/2，则此时选择第二个数（舍弃第一个数）的概率设为1/2就可以了；如果再新增一个数，要保证从最终看来这三个数被抽中的概率都是1/3则只需要以1/3的概率选择第三个数就可以了。因为从最终看来第一个数被选择的概率P=1*(1/2)*（2/3）=1/3，第二个数被选择的概率P=(1/2)*(2/3)=1/3。

依次类推，对于第i个出现的元素，我们只需要以1/i的概率选择它就可以保证全部i个元素被选中的概率是相同的。这在不确定符合条件的目标的数量时就要做选择时非常有用。

import java.util.Random;

public class No398_RandomPickIndex {
    private final int[] nums;
    private final Random random = new Random();

    public No398_RandomPickIndex(int[] nums) {
        this.nums = nums;
    }

    public int pick(int target) {
        //index用于选取最终要返回的下标，appearance用于保存目标数已经出现的次数
        int index = 0, appearance = 0;
        for (int i = 0; i < nums.length; i++) {
            //以出现的目标数为蓄水池中的元素
            if (nums[i] == target) {
                appearance++;
                //抽取第appearance个数的概率为1/appearance
                if (random.nextInt(appearance)+1==1)
                    index=i;
            }
        }
        return index;
    }
}

LeetCode 382. 链表随机节点 (opens new window)

题目描述

给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。保证每个节点被选的概率一样。

进阶: 如果链表十分大且长度未知，如何解决这个问题？你能否使用常数级空间复杂度实现？

示例

// 初始化一个单链表 [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom()方法应随机返回1,2,3中的一个，保证每个元素被返回的概率相等。
solution.getRandom();

解题思路

这一题地思路就和上一题中地蓄水池抽样问题地场景相吻合。

import java.util.Random;

public class No382_LinkedListRandomNode {
    private final ListNode head;
    private final Random random = new Random();

    public No382_LinkedListRandomNode(ListNode head) {
        this.head = head;
    }

    /** Returns a random node's value. */
    public int getRandom() {
        int appearance = 1, selectedValue = 0;
        ListNode temp = head;
        while (temp != null) {
            //也可以不用Random类，用(int)(appearance * Math.random()) == 0
            if (random.nextInt(appearance) + 1 == 1)
                selectedValue = temp.val;
            temp = temp.next;
            appearance++;
        }
        return selectedValue;
    }


    public static void main(String args[]) {
        No382_LinkedListRandomNode ins = new No382_LinkedListRandomNode(new ListNode(1));
        System.out.println(ins.getRandom());
    }
}