简述游戏中常用的两种随机算法（上）
没事儿的时候我喜欢玩玩那些经典的 2d 网页小游戏，我发现很多游戏都要涉及地图的随机生成，比如扫雷游戏中地雷的位置应该是随机分布的：
再比如经典炸弹人游戏，障碍物的位置也是有一定随机性的：
这些 2d 游戏相较现在的大型 3d 游戏虽然看起来有些简陋，但依然用到很多有趣算法技巧，本文就来深入研究一下地图的随机生成算法。
2d 游戏的地图肯定可以抽象成一个二维矩阵，就拿扫雷举例吧，我们可以用下面这个类表示扫雷的棋盘：
class game { int m, n; // 大小为 m * n 的二维棋盘 // 值为 true 的地方代表有雷，false 代表没有雷 boolean[][] board;}如果你想在棋盘中随机生成k个地雷，也就是说你需要在board中生成k个不同的(x, y)坐标，且这里面x, y都是随机生成的。
对于这个需求， 首先一个优化就是对二维矩阵进行「降维打击」，把二维数组转化成一维数组 ：
class game { int m, n; // 长度为 m * n 的一维棋盘 // 值为 true 的地方代表有雷，false 代表没有雷 boolean[] board; // 将二维数组中的坐标 (x, y) 转化为一维数组中的索引 int encode(int x, int y) { return x * n + y; } // 将一维数组中的索引转化为二维数组中的坐标 (x, y) int[] decode(int index) { return new int[] {index / n, index % n}; }}这样，我们只要在[0, m * n)中选取一个随机数，就相当于在二维数组中随机选取了一个元素。
但问题是，我们现在需要随机选出k个不同的位置放地雷。你可能说，那在[0, m * n)中选出来k个随机数不就行了？
是的，但实际操作起来有些麻烦，因为你很难保证随机数不重复。如果出现重复的随机数，你就得再随机选一次，直到找到k个不同的随机数。
如果k比较小m * n比较大，那出现重复随机数的概率还比较低，但如果k和m * n的大小接近，那么出现重复随机数的概率非常高，算法的效率就会大幅下降。
那么，我们有没有更好的办法能够在线性的时间复杂度解决这个问题？其实是有的，而且有很多种解决方案。
洗牌算法第一个解决方案，我们可以换个思路，避开「在数组中随机选择k个元素」这个问题，把问题转化成「如何随机打乱一个数组」 。
现在想随机初始化k颗地雷的位置，你可以先把这k颗地雷放在board开头，然后把board数组随机打乱，这样地雷不就随机分布到board数组的各个地方了吗？
洗牌算法，或者叫随机乱置算法就是专门解决这个问题的，我们可以看下力扣第 384 题「打乱数组」：
这个shuffle函数是算法的关键，直接看解法代码吧：
class solution { private int[] nums; private random rand = new random(); public solution(int[] nums) { this.nums = nums; } public int[] reset() { return nums; } // 洗牌算法 public int[] shuffle() { int n = nums.length; int[] copy = arrays.copyof(nums, n); for (int i = 0 ; i < n; i++) { // 生成一个 [i, n-1] 区间内的随机数 int r = i + rand.nextint(n - i); // 交换 nums[i] 和 nums[r] swap(copy, i, r); } return copy; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}洗牌算法的时间复杂度是 o(n)，而且逻辑很简单，关键在于让你证明为什么这样做是正确的。排序算法的结果是唯一可以很容易检验的，但随机乱置算法不一样，乱可以有很多种，你怎么能证明你的算法是「真的乱」呢？
分析洗牌算法正确性的准则：产生的结果必须有n!种可能 。这个很好解释，因为一个长度为n的数组的全排列就有n!种，也就是说打乱结果总共有n!种。算法必须能够反映这个事实，才是正确的。
有了这个原则再看代码应该就容易理解了：
对于nums[0]，我们把它随机换到了索引[0, n)上，共有n种可能性；
对于nums[1]，我们把它随机换到了索引[1, n)上，共有n - 1种可能性；
对于nums[2]，我们把它随机换到了索引[2, n)上，共有n - 2种可能性；
以此类推，该算法可以生成n!种可能的结果，所以这个算法是正确的，能够保证随机性。
水塘抽样算法学会了洗牌算法，扫雷游戏的地雷随机初始化问题就解决了。不过别忘了，洗牌算法只是一个取巧方案，我们还是得面对「在若干元素中随机选择k个元素」这个终极问题。
要知道洗牌算法能够生效的前提是你使用数组这种数据结构，如果让你在一条链表中随机选择k个元素，肯定不能再用洗牌算法来蒙混过关了。
再比如，假设我们的扫雷游戏中棋盘的长和宽非常大，已经不能在内存中装下一个大小为m * n的board数组了，我们只能维护一个大小为k的数组记录地雷的位置：
class game { // 棋盘的行数和列数（非常大） int m, n; // 长度为 k 的数组，记录 k 个地雷的一维索引 int[] mines; // 将二维数组中的坐标 (x, y) 转化为一维数组中的索引 int encode(int x, int y) { return x * n + y; } // 将一维数组中的索引转化为二维数组中的坐标 (x, y) int[] decode(int index) { return new int[] {index / n, index % n}; }}这样的话，我们必须想办法在[0, m*n)中随机选取k个不同的数字了。
这就是常见的随机抽样场景，常用的解法是水塘抽样算法（reservoir sampling） 。水塘抽样算法是一种随机概率算法，会者不难，难者不会。
我第一次见到这个算法问题是谷歌的一道算法题：给你一个未知长度的单链表，请你设计一个算法， 只能遍历一次 ，随机地返回链表中的一个节点。
这里说的随机是均匀随机（uniform random），也就是说，如果有n个元素，每个元素被选中的概率都是1/n，不可以有统计意义上的偏差。
一般的想法就是，我先遍历一遍链表，得到链表的总长度n，再生成一个[0,n-1)之间的随机数为索引，然后找到索引对应的节点。但这不符合只能遍历一次链表的要求。
这个问题的难点在于随机选择是「动态」的，比如说你现在你已经遍历了 5 个元素，你已经随机选取了其中的某个元素a作为结果，但是现在再给你一个新元素b，你应该留着a还是将b作为结果呢？以什么逻辑做出的选择，才能保证你的选择方法在概率上是公平的呢？
kindle没电了充电一直显示感叹号
Arteris推出下一代FlexNoC 5物理感知片上网络IP
一级页表虚拟地址转换为物理地址示例
半导体何时复苏？分析师：无法预测！
德索共享HSD线束加工材料选择
简述游戏中常用的两种随机算法（上）
西门子发布Tessent RTL Pro加速下一代关键可测试性设计任务
室内空气污染物监测设计和工作原理
深圳触觉智能「全国产化主板」大盘点（一）
电动机的主要分类有哪些
蒲公英工业4G路由器助力共享停车突破瓶颈
2023年最好用的智能手表盘点：炫酷指南，探索佩戴的极致
凌力尔特公司推出电路保护控制器 LTC4368
高通发布骁龙675，成中高端手机标配
iPhone8什么时候上市：iPhone8因技术难题或难产，果粉们怎么看
59N6-TE机动型雷达受到国外客户的欢迎
基于管理和组合HDL电路单元IP库的HAD辅助设计软件研究
物联网产业近年来迎来爆炸式增长，安全现状却令人堪忧
茂硕发布新一代智能LED驱动电源
Intel计划月底选出新任CEO，或将由女性领导
再比如经典炸弹人游戏，障碍物的位置也是有一定随机性的：
这些 2d 游戏相较现在的大型 3d 游戏虽然看起来有些简陋，但依然用到很多有趣算法技巧，本文就来深入研究一下地图的随机生成算法。
2d 游戏的地图肯定可以抽象成一个二维矩阵，就拿扫雷举例吧，我们可以用下面这个类表示扫雷的棋盘：
class game { int m, n; // 大小为 m * n 的二维棋盘 // 值为 true 的地方代表有雷，false 代表没有雷 boolean[][] board;}如果你想在棋盘中随机生成k个地雷，也就是说你需要在board中生成k个不同的(x, y)坐标，且这里面x, y都是随机生成的。
对于这个需求， 首先一个优化就是对二维矩阵进行「降维打击」，把二维数组转化成一维数组 ：
class game { int m, n; // 长度为 m * n 的一维棋盘 // 值为 true 的地方代表有雷，false 代表没有雷 boolean[] board; // 将二维数组中的坐标 (x, y) 转化为一维数组中的索引 int encode(int x, int y) { return x * n + y; } // 将一维数组中的索引转化为二维数组中的坐标 (x, y) int[] decode(int index) { return new int[] {index / n, index % n}; }}这样，我们只要在[0, m * n)中选取一个随机数，就相当于在二维数组中随机选取了一个元素。
但问题是，我们现在需要随机选出k个不同的位置放地雷。你可能说，那在[0, m * n)中选出来k个随机数不就行了？
是的，但实际操作起来有些麻烦，因为你很难保证随机数不重复。如果出现重复的随机数，你就得再随机选一次，直到找到k个不同的随机数。
如果k比较小m * n比较大，那出现重复随机数的概率还比较低，但如果k和m * n的大小接近，那么出现重复随机数的概率非常高，算法的效率就会大幅下降。
那么，我们有没有更好的办法能够在线性的时间复杂度解决这个问题？其实是有的，而且有很多种解决方案。
洗牌算法第一个解决方案，我们可以换个思路，避开「在数组中随机选择k个元素」这个问题，把问题转化成「如何随机打乱一个数组」 。
现在想随机初始化k颗地雷的位置，你可以先把这k颗地雷放在board开头，然后把board数组随机打乱，这样地雷不就随机分布到board数组的各个地方了吗？
洗牌算法，或者叫随机乱置算法就是专门解决这个问题的，我们可以看下力扣第 384 题「打乱数组」：
这个shuffle函数是算法的关键，直接看解法代码吧：
class solution { private int[] nums; private random rand = new random(); public solution(int[] nums) { this.nums = nums; } public int[] reset() { return nums; } // 洗牌算法 public int[] shuffle() { int n = nums.length; int[] copy = arrays.copyof(nums, n); for (int i = 0 ; i < n; i++) { // 生成一个 [i, n-1] 区间内的随机数 int r = i + rand.nextint(n - i); // 交换 nums[i] 和 nums[r] swap(copy, i, r); } return copy; } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }}洗牌算法的时间复杂度是 o(n)，而且逻辑很简单，关键在于让你证明为什么这样做是正确的。排序算法的结果是唯一可以很容易检验的，但随机乱置算法不一样，乱可以有很多种，你怎么能证明你的算法是「真的乱」呢？
分析洗牌算法正确性的准则：产生的结果必须有n!种可能 。这个很好解释，因为一个长度为n的数组的全排列就有n!种，也就是说打乱结果总共有n!种。算法必须能够反映这个事实，才是正确的。
有了这个原则再看代码应该就容易理解了：
对于nums[0]，我们把它随机换到了索引[0, n)上，共有n种可能性；
对于nums[1]，我们把它随机换到了索引[1, n)上，共有n - 1种可能性；
对于nums[2]，我们把它随机换到了索引[2, n)上，共有n - 2种可能性；
以此类推，该算法可以生成n!种可能的结果，所以这个算法是正确的，能够保证随机性。
水塘抽样算法学会了洗牌算法，扫雷游戏的地雷随机初始化问题就解决了。不过别忘了，洗牌算法只是一个取巧方案，我们还是得面对「在若干元素中随机选择k个元素」这个终极问题。
要知道洗牌算法能够生效的前提是你使用数组这种数据结构，如果让你在一条链表中随机选择k个元素，肯定不能再用洗牌算法来蒙混过关了。
再比如，假设我们的扫雷游戏中棋盘的长和宽非常大，已经不能在内存中装下一个大小为m * n的board数组了，我们只能维护一个大小为k的数组记录地雷的位置：
class game { // 棋盘的行数和列数（非常大） int m, n; // 长度为 k 的数组，记录 k 个地雷的一维索引 int[] mines; // 将二维数组中的坐标 (x, y) 转化为一维数组中的索引 int encode(int x, int y) { return x * n + y; } // 将一维数组中的索引转化为二维数组中的坐标 (x, y) int[] decode(int index) { return new int[] {index / n, index % n}; }}这样的话，我们必须想办法在[0, m*n)中随机选取k个不同的数字了。
这就是常见的随机抽样场景，常用的解法是水塘抽样算法（reservoir sampling） 。水塘抽样算法是一种随机概率算法，会者不难，难者不会。
我第一次见到这个算法问题是谷歌的一道算法题：给你一个未知长度的单链表，请你设计一个算法， 只能遍历一次 ，随机地返回链表中的一个节点。
这里说的随机是均匀随机（uniform random），也就是说，如果有n个元素，每个元素被选中的概率都是1/n，不可以有统计意义上的偏差。
一般的想法就是，我先遍历一遍链表，得到链表的总长度n，再生成一个[0,n-1)之间的随机数为索引，然后找到索引对应的节点。但这不符合只能遍历一次链表的要求。
这个问题的难点在于随机选择是「动态」的，比如说你现在你已经遍历了 5 个元素，你已经随机选取了其中的某个元素a作为结果，但是现在再给你一个新元素b，你应该留着a还是将b作为结果呢？以什么逻辑做出的选择，才能保证你的选择方法在概率上是公平的呢？
kindle没电了充电一直显示感叹号
Arteris推出下一代FlexNoC 5物理感知片上网络IP
一级页表虚拟地址转换为物理地址示例
半导体何时复苏？分析师：无法预测！
德索共享HSD线束加工材料选择
简述游戏中常用的两种随机算法（上）
西门子发布Tessent RTL Pro加速下一代关键可测试性设计任务
室内空气污染物监测设计和工作原理
深圳触觉智能「全国产化主板」大盘点（一）
电动机的主要分类有哪些
蒲公英工业4G路由器助力共享停车突破瓶颈
2023年最好用的智能手表盘点：炫酷指南，探索佩戴的极致
凌力尔特公司推出电路保护控制器 LTC4368
高通发布骁龙675，成中高端手机标配
iPhone8什么时候上市：iPhone8因技术难题或难产，果粉们怎么看
59N6-TE机动型雷达受到国外客户的欢迎
基于管理和组合HDL电路单元IP库的HAD辅助设计软件研究
物联网产业近年来迎来爆炸式增长，安全现状却令人堪忧
茂硕发布新一代智能LED驱动电源
Intel计划月底选出新任CEO，或将由女性领导