384. 打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。
实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象
• int[] reset() 重设数组到它的初始状态并返回
• int[] shuffle() 返回数组随机打乱后的结果

示例：

输入
["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]

提示：

• 1 <= nums.length <= 200
• -10^6 <= nums[i] <= 10^6
• nums 中的所有元素都是 唯一的
• 最多可以调用 5 * 10^4 次 reset 和 shuffle

解法一：全排列（超内存，超时）

type Solution struct {
    initSlice []int
    curSlice  []int
    fullSlice [][]int
}

func Constructor(nums []int) Solution {
    var curSlice = make([]int, len(nums))
    copy(curSlice, nums)
    return Solution{
        initSlice: nums,
        curSlice:  curSlice,
        fullSlice: permute(nums),
    }
}

func permute(nums []int) [][]int {
    var res [][]int
    var cur []int
    used := make([]bool, len(nums))
    recursion(cur, &used, nums, &res)
    return res
}

func recursion(cur []int, used *[]bool, nums []int, res *[][]int) {
    fmt.Println(cur)
    if len(cur) == len(nums) {
        temp := make([]int, len(nums))
        copy(temp, cur)
        *res = append(*res, temp)
        return
    }
    for i, val := range nums {
        if !(*used)[i] {
            (*used)[i] = true
            cur = append(cur, val)
            recursion(cur, used, nums, res)
            cur = cur[:len(cur)-1]
            (*used)[i] = false
        }
    }
    return
}

func (this *Solution) Reset() []int {
    return this.initSlice
}

func (this *Solution) Shuffle() []int {
    return this.fullSlice[rand.Intn(len(this.fullSlice))]
}

解法二：洗牌算法（从后往前）

type Solution struct {
    initSlice []int
    curSlice  []int
}

func Constructor(nums []int) Solution {
    var curSlice = make([]int, len(nums))
    copy(curSlice, nums)
    return Solution{
        initSlice: nums,
        curSlice:  curSlice,
    }
}

func (this *Solution) Reset() []int {
    return this.initSlice
}

func (this *Solution) Shuffle() []int {
    n := len(this.curSlice)
    for i := n - 1; i >= 0; i-- {
        j := rand.Intn(i + 1)
        this.curSlice[i], this.curSlice[j] = this.curSlice[j], this.curSlice[i]
    }
    return this.curSlice
}

解法三：洗牌算法（从前往后）

type Solution struct {
    initSlice []int
    curSlice  []int
}

func Constructor(nums []int) Solution {
    var curSlice = make([]int, len(nums))
    copy(curSlice, nums)
    return Solution{
        initSlice: nums,
        curSlice:  curSlice,
    }
}

func (this *Solution) Reset() []int {
    return this.initSlice
}

func (this *Solution) Shuffle() []int {
    n := len(this.curSlice)
    for i := range this.curSlice {
        j := i + rand.Intn(n-i)
        this.curSlice[i], this.curSlice[j] = this.curSlice[j], this.curSlice[i]
    }
    return this.curSlice
}