384. Shuffle an Array

c++ random函数：https://www.jb51.net/article/124108.htm

rand()不需要参数，它会返回一个从0到最大随机数的任意整数，最大随机数的大小通常是固定的一个大整数。这样，如果你要产生0~10的10个整数，可以表达为：

int N = rand() % 11;

这样，N的值就是一个0~10的随机数，如果要产生1~10，则是这样：

总结来说，可以表示为：

a + rand() % n

其中的a是起始值，n是整数的范围。

https://www.cnblogs.com/grandyang/p/5783392.html

Knuth shuffle算法：

https://yjk94.wordpress.com/2017/03/17/%E6%B4%97%E7%89%8C%E7%9A%84%E6%AD%A3%E7%A1%AE%E5%A7%BF%E5%8A%BF-knuth-shuffle%E7%AE%97%E6%B3%95/

不能直接随机取数字，只能随机取之前的数字才能保证等概率。

注意：取余i+1才能取到为i的余数。遍历到i的时候，必须有交换i自己这一项，所以必须是i+1。

https://leetcode.com/problems/shuffle-an-array/discuss/85965/C++-Knuth-Shuffle-(Fisher-Yates-Shuffle)-Implementation-(352-ms)

class Solution {

public:

    Solution(vector<int> nums){

        for(auto num : nums)

            v.push_back(num);

    }

    /** Resets the array to its original configuration and return it. */

    vector<int> reset() {

        return v;

    }

    /** Returns a random shuffling of the array. */

    vector<int> shuffle() {

        vector<int> res = v;

        for (int i = ; i < res.size(); ++i) {

            int t = rand() % (i + );

            swap(res[i], res[t]);

        }

        return res;

    }

private:

    vector<int> v;

};

巴特西

leetcode 384. Shuffle an Array

Knuth shuffle算法：

最新文章

热门文章