2021-11-11：打乱数组。给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。实现 Solution cl

福大大架构师每日一题

发布于 2021-11-16 10:33:35

5200

发布于 2021-11-16 10:33:35

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
}

执行结果如下：