|

384.Fisher-Yates 洗牌算法

蛮有意思的一道题,Fisher-Yates 洗牌算法是诸多shuffle的标准操作,其流程也很简单:遍历下标i∈[0, n),随机选择j∈[i, n),交换i与j指向的内容,即可实现在O(n)时间打乱数组,且任何原数组的排列返回的概率相同,写成代码如下:

type Solution struct {
    nums []int
    raw_nums []int
}



func Constructor(nums []int) Solution {
    raw_nums := make([]int, len(nums), len(nums))
    copy(raw_nums, nums)
    solution := Solution{
        nums,
        raw_nums,
    }
    return solution
}


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


func (this *Solution) Shuffle() []int {
    for i:=0;i<len(this.nums);i++{
        j := rand.Intn(len(this.nums)-i)+i
        this.nums[i],this.nums[j] = this.nums[j],this.nums[i]
    }

    return this.nums
}


/**
 * Your Solution object will be instantiated and called as such:
 * obj := Constructor(nums);
 * param_1 := obj.Reset();
 * param_2 := obj.Shuffle();
 */

这里有个小技巧,copy一份源数组作为reset的返回,时间换空间。

类似文章

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注