随机、模拟、概率

Leetcode的一道题

一切要从这道题说起。

重复n次的元素
题目为：

	给你一个整数数组 nums ，该数组具有以下属性：
	nums.length == 2 * n
	nums 包含 n + 1 个 不同的 元素
	nums 中恰有一个元素重复 n 次
	找出并返回重复了 n 次的那个元素。

思路

记重复 n 次的元素为 xx。由于数组 $\text{nums}$ 中有 n+1 个不同的元素，而其长度为 2n，那么数组中剩余的元素均只出现了一次。也就是说，我们只需要找到重复出现的元素即为答案。

解法一
这道题第一反应是用哈希表来做，实际上官网题解中也有一个哈希表的解法。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        found = set()			# 建立一个空集合
        for num in nums:		# 枚举给定数组内每个元素
            if num in found:	# 判断集合内是否已存在该元素
                return num
            found.add(num)		# 将新元素放入集合内
        # 不可能的情况
        return -1

解法二
这道题巧妙的地方在于官方给出的另外一种解法，即蒙特卡洛解法（随机法）。由题可知，给定的数组内一半的数据相同，所以要找出两个相同的数据在概率上而言并不难。在 n 趋于无穷大时，该期望值为4，所以该算法的时间复杂度仅为 O(1)。

class Solution:
    def repeatedNTimes(self, nums: List[int]) -> int:
        n = len(nums)
        while True:
            x, y = random.randrange(n), random.randrange(n)
            if x != y and nums[x] == nums[y]:
                return nums[x]

这种随机的思想，让我想到了数学建模中的一个常用算法 —— 蒙特卡洛算法

蒙特卡洛算法

蒙特卡洛算法是一种统计模拟方法，是一种数值计算方法。例如，法国数学家Buffon通过随机投针的方法计算圆周率 $\pi$ ，将代数问题转换成几何问题。当样本足够大时，可以更接近最优解。

蒙特卡洛算法的流程分为三部分。

1. 构造随机的概率过程
2. 从已知概率分布抽样
3. 求解估计量

此算法适用于一些可以模拟降低问题的复杂性，在数学、增强学习、金融工程学，宏观经济学，计算物理学等领域应用广泛，往往配合随机过程、博弈论等应用。
可以参考该文章 “蒙特卡洛在投资理财领域的应用”。
另外在人工智能、智能决策等领域用的比较多的还有 蒙特卡洛树搜索法，比如Alphago。