2021-11-11：打乱数组。给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。实现 Solution class:Solutio(int[] nums) 使用整数数组 nums

2021-11-11：打乱数组。给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。实现 Solution class:Solutio(int[] nums) 使用整数数组 nums 初始化对象；int[] reset() 重设数组到它的初始状态并返回；int[] shuffle() 返回数组随机打乱后的结果 。力扣384。

答案2021-11-11：

第1次，1到N-1取随机数i1，[i1]与[N-1]交换。
第2次，1到N-2取随机数i2，[i2]与[N-2]交换。
遍历下去，就是打乱的数组了。
时间复杂度：O(N)。
额外空间复杂度：O(N)。因为有重置功能。

代码用golang编写。代码如下：

package main

import (

    "fmt"

    "math/rand"

    "time"

)

func main() {

    rand.Seed(time.Now().UnixNano())

    arr := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

    c := Constructor(arr)

    fmt.Println(c.Shuffle())

}

type Solution struct {

    origin  []int

    shuffle []int

    N       int

}

func Constructor(nums []int) Solution {

    res := Solution{}

    res.origin = nums

    res.N = len(nums)

    res.shuffle = make([]int, res.N)

    for i := 0; i < res.N; i++ {

        res.shuffle[i] = res.origin[i]

    }

    return res

}

func (this *Solution) Reset() []int {

    return this.origin

}

func (this *Solution) Shuffle() []int {

    for i := this.N - 1; i >= 0; i-- {

        //int r = (int) (Math.random() * (i + 1));

        r := rand.Intn(i + 1)

        tmp := this.shuffle[r]

        this.shuffle[r] = this.shuffle[i]

        this.shuffle[i] = tmp

    }

    return this.shuffle

}

执行结果如下：

左神java代码

2021-11-11：打乱数组。给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。实现 Solution class:Solutio(int[] nums) 使用整数数组 nums的相关教程结束。