**问题**：在一些场合中，我们需要知道模拟真实世界中的随机，一个基础的问题是：怎么在已知数据集上随机返回一个结果。 ? 参考问题：https://leetcode.com/problems/shuffle-an-array/先看一下开源代码中Random的代码
public int nextInt(int bound) {
? ? ? ? if (bound <= 0)
? ? ? ? ? ? throw new IllegalArgumentException(BadBound);
? ? ? ? int r = next(31);
? ? ? ? int m = bound - 1;
? ? ? ? if ((bound & m) == 0) ?// i.e., bound is a power of 2
? ? ? ? ? ? r = (int)((bound * (long)r) >> 31);
? ? ? ? else {
? ? ? ? ? ? for (int u = r;
? ? ? ? ? ? ? ? ?u - (r = u % bound) + m < 0;
? ? ? ? ? ? ? ? ?u = next(31))
? ? ? ? ? ? ? ? ;
? ? ? ? }
? ? ? ? return r;
? ? }
Java中Random()对象是生成随机数的对象。Random()有两种构造方法：
? ? ? ?Random()：创建一个新的随机数生成器，这种方式采用默认的种子。
? ? ? ?Random(long seed)：使用seed为种子创建一个新的随机数生成器。 ? ?
种子的作用：我们在创建Random对象的时候，如果不设定种子，对象会采用默认的种子（默认当前系统时间的毫秒数为种子）。
? ? ? ? Random()对象生成的随机数是伪随机数（通过算法产生的随机数都是伪随机数，满足统计学上的误差要求，认为它是真随机），这就意味着如果我们知道了种子，或者已经产生的随机数，都可能获得接下来随机序列的信息（这样就使得随机数有了可预测性，如果种子数一样，则会生成相同的随机数，具体可以看：案例1）。只有通过真实的随机时间产生的随机数才是真随机。例如通过机器的硬件噪声来产生的随机数、通过当前环境pm10数据产生的随机数。虽然两种构造方法都是伪随机，但是无参的构造方法具有更强的随机性，能满足一般统计上的随机数要求。另外，种子数只是随机算法的起源数字，和生成的随机数没有任何关系，可以随意设置合法的种子数。
? ? ? ?
? ? ? 对于数组{a1,a2,.......an} , 要做到每个排列真正的随机出现，每个排列出现的概率为??,参考算法导论第三版71页的引理5.5, 在O(N)的时间复杂度下，实现随机返回一个序列，可以在for循环里对当前位置元素与其后面元素做交换。 证明比较复杂，用到了数学归纳法。
class Solution {
private int[] nums;
private Random random;
public Solution(int[] nums) {
this.nums = nums;
random = new Random();
}
/**
* Resets the array to its original configuration and return it.
*/
public int[] reset() {
return nums;
}
/**
* Returns a random shuffling of the array.
*/
public int[] shuffle() {
if (nums == null) return null;
int[] a = nums.clone();
for (int j = 0; j < a.length; j++) {
int i = j + random.nextInt(a.length - j);
swap(a, i, j);
}
return a;
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}这里算法的精髓就是以下几行：
for (int j = 0; j < a.length; j++) {
int i = j + random.nextInt(a.length - j);
swap(a, i, j);
}
