所有题解方法请移步 github-Leecode_summary
384.打乱数组 & 398.随机数索引
set() 看似无序却有序，看似有序却无序
写在前面：
之前做127题单词接龙时被set()时间复杂度折磨了很久，所以看到无序就想，这不是set()就好了 ( 当然没这么easy，不过set()无序问题水真深….，所以题目应该是手动实现random.shuffle吧。
看完题解：
哦，原来还有洗牌算法这么一说 ==
盘一波洗牌算法： 我又来当搬运工了： 三种洗牌算法shuffle，介绍了384的洗牌解法和398的蓄水池解法。这个题解也说的蛮不错，而且用蒙特卡洛方法验证Fisher-Yates的有效性。
- Python版本 Knuth-Durstenfeld Shuffle 写法：
1
2
3
4
5
6
7
8
9
10
11
12import 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
实例面试题：如何从二进制文件中随机取整数？(要求等概率)
1
2
3
4
5
6
7
8
9# 方法一： 上面洗牌算法链接中的一个,适合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.常数时间插入、删除和获取
没啥好说的呀，写就完事了，有几点疑问：
- 382我写的不知道是不是常数级空间复杂度
- 380为什么要用hashmap(dict)，
i in set()本身就是一个O(1)问题，有点搞不懂 希望有人看到来解答一波吧~