【leetcode】384 Shuffle an Array

发表于 | 分类于 ，

从所有排列中等概率随机选一个


描述

从所有排列中等概率随机选一个

样例

1
2
输入: [1,2,3]
输出: [1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,2,1],[3,1,2] 随机一个

思路

随机产生位置进行交换，交换次数开始选的是 100 ，后来改成了 nums.size() * 2,注意随机数std::uniform_int_distribution<int> u (0, origin.size()-1);右端不能小于 0 。交换数组可以用函数 swap(a,b) 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private:
        vector<int>origin;

    public:
        Solution(vector<int> nums) {
            origin.assign(nums.begin(), nums.end());
        }

        /** Resets the array to its original configuration and return it. */
        vector<int> reset() {
            return origin;
        }

        /** Returns a random shuffling of the array. */
        vector<int> shuffle() {
            vector<int> shuffleArray(origin);
            if (shuffleArray.size() == 0) { return shuffleArray; }
            static default_random_engine e(time(0));
            std::uniform_int_distribution<int> u (0, origin.size()-1);
            for (int i = 0; i < origin.size()*2; i++) {
                int ind1 = u(e), ind2 = u(e);
                swap(shuffleArray[ind1], shuffleArray[ind2]);
            }
            return shuffleArray;
        }
    };

参考

原题链接