LC吐血整理之Random篇

所有题解方法请移步 github-Leecode_summary

384.打乱数组 & 398.随机数索引

set() 看似无序却有序，看似有序却无序
写在前面：
　　之前做127题单词接龙时被set()时间复杂度折磨了很久，所以看到无序就想，这不是set()就好了 ( 当然没这么easy，不过set()无序问题水真深....，所以题目应该是手动实现random.shuffle吧。
看完题解：
　　哦，原来还有洗牌算法这么一说 ==

盘一波洗牌算法：
　　我又来当搬运工了： 三种洗牌算法shuffle，介绍了384的洗牌解法和398的蓄水池解法。这个题解也说的蛮不错，而且用蒙特卡洛方法验证Fisher-Yates的有效性。

• Python版本 Knuth-Durstenfeld Shuffle 写法：

import random
def shuffle(List):
    n = len(List)
    # 方法一： (n-1)/n*(n-2)/(n-1)···*1/(n-i+1) = 1/n
    # 从前往后遍历，适合List动态变化或者List长度未知的情况
    for i in range(n): / range(n-1)  # i = n-1实际上只有一个坑位
        swap = random.randrange(i, n)
        List[swap]. List[i] = list[i], List[swap]  # 这里是修改的原数组List 有需要的话先copy
    # 方法二：只是方向的区别 
    for i in range(n-1, -1, -1): / range(n-1, 0, -1)
        swap = random.randrange(0, i)
        List[swap]. List[i] = list[i], List[swap]

• Python版本 蓄水池抽样算法：
  基本要求: 随机从容量为N的数组中抽取k个元素，要求等概率抽样也就是k/N
  实例面试题：如何从二进制文件中随机取整数？(要求等概率)

# 方法一： 上面洗牌算法链接中的一个,适合List动态变化
# 选中概率：
# 1. 后面k-n出现在前k个的概率：k/(k+1)*(k+1)/k+2*···*(n-1)/n
# 2. 前面0-k出现在k个的概率：k/n
def shufflek(List, l):
    for i in range(k, len(List)):
        swap = random.randrange(0, i)
        if swap < k:
            List[swap]. List[i] = list[i], List[swap]

382.链表随机节点 & 380.常数时间插入、删除和获取

没啥好说的呀，写就完事了，有几点疑问：

1. 382我写的不知道是不是常数级空间复杂度
2. 380为什么要用hashmap(dict)，i in set() 本身就是一个O(1)问题，有点搞不懂
   希望有人看到来解答一波吧~