384. 打乱数组(中)

• 题目
• 法一、 Fisher-Yates
• 法二、鸽尾式洗牌法（Riffle Shuffle）

题目

• 给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。
  实现 Solution class:
  Solution(int[] nums) 使用整数数组 nums 初始化对象
  int[] reset() 重设数组到它的初始状态并返回
  int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]
解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

法一、 Fisher-Yates

• 原理：从最后一个元素开始，在之前的位置随机选一个与之交换，往前一位继续此操作直到第一位。

import random

class Solution:
    def __init__(self, nums):  #构造函数
        self.nums = nums  #将传入的数组赋值给类的成员变量self.nums

    def reset(self):
        return self.nums  #返回存储在self.nums中的原始数组

    def shuffle(self):
        temp = list(self.nums) #将原始数组self.nums的内容复制到临时数组temp中
        n = len(temp)
        for i in range(n - 1, 0, -1):  #从最后一个元素到第一个元素的循环
            # 随机选择一个位置
            j = random.randint(0, i)   #表示取0-i之间的一个整数
            # 交换当前位置元素和随机选择的位置元素
            temp[i], temp[j] = temp[j], temp[i]
        return temp

法二、鸽尾式洗牌法（Riffle Shuffle）

• 原理：将数组一分为二，再穿插合并，再不断重复这样的操作

import random

class Solution:
    def __init__(self, nums):
        self.nums = nums

    def reset(self):
        return self.nums

    def shuffle(self):
        temp = list(self.nums)   #将原始数组self.nums的内容复制到临时数组temp中
        n = len(temp)
        mid = n // 2  # 找到数组的中间位置，使用整数除法来确保中间位置是一个整数

        # 迭代洗牌操作
        for i in range(mid):
            # 随机选择一个插入点
            j = random.randint(i, mid + i)
            
            # 将第二堆的牌插入到第一堆中
            temp[i], temp[j] = temp[j], temp[i]

        return temp  #返回洗牌后的数组temp