记录一道有意思的算法题

[TOC]

给你一个从0开始的递增数组，将其随机打乱成另一个数组并返回。#字节#

要求使用O(1)空间内解决该问题

解决交换的次数越多随机数随到已经交换的下标的可能性越大的问题

该算法已有标准实现，可以自己看看

单纯从题目不加限制条件的角度来做，可以想到暴力法。标准实现还得看洗牌算法。

暴力法:申请另一个数组
Fisher-Yates 洗牌算法：

我们可以在移除 waiting 的第 k个元素时，将第 k个元素与数组的最后 1个元素交换，然后移除交换后数组的最后 1个元素，这样我们只需要 O(1) 的时间复杂度即可完成移除第 k 个元素的操作。此时，被移除的交换后数组的最后 1 个元素即为我们根据随机下标获取的元素。

在此基础上，我们也可以不移除最后 1 个元素，而直接将其作为乱序后的结果，并更新待乱序数组的长度，从而实现数组的原地乱序。因为我们不再需要从数组中移除元素，所以也可以将第 k 个元素与第 1 个元素交换。

1
2
3

/*
代码同下
*/

Knuth 洗牌算法：

在 O(n) 复杂度内等概率返回某个方案。

具体的，我们从前往后尝试填充 [0,n−1] 该填入什么数时，通过随机当前下标与（剩余的）哪个下标进行值交换来实现。

对于下标 x 而言，我们从 [x,n−1] 中随机出一个位置与 x 进行值交换，当所有位置都进行这样的处理后，我们便得到了一个公平的洗牌方案。

这样能确保每个元素在每个位置的概率都是1/n。

class Solution {
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
    
    vector<int> shuffle() {
        for (int i = 0; i < nums.size(); ++i) {
            int j = i + rand() % (nums.size() - i);
            swap(nums[i], nums[j]);
        }
        return nums;
    }

private:
    vector<int> nums;
    vector<int> original;
}

解答参考链接：

[1]:https://blog.csdn.net/cy973071263/article/details/128818181 “参考链接1”
[2]:https://blog.csdn.net/defaultbyzt/article/details/128628119 “参考链接2”
[3]:https://www.bilibili.com/read/cv26024350/ “参考链接3”
[4]:https://leetcode.cn/problems/shuffle-an-array/ “参考链接4”