LeetCode:384. Shuffle an Array、乱数生成(C++)

3353 ワード

見出し
Shuffle a set of numbers without duplicates.
Example:
//Init an array with set 1, 2, and 3. int[] nums = {1,2,3}; Solution solution = new Solution(nums);
//Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. solution.shuffle();
//Resets the array back to its original configuration [1,2,3]. solution.reset();
//Returns the random shuffling of array [1,2,3]. solution.shuffle();
1、シャッフル:現在のインデックスiと(i,n-1)の乱数pos対応値を交換します.このように与えられた結果は等概であるべきである.2、乱数:A、上記の説明では複雑なようですが、そうではありません.(0,n-1)で乱数を選択するたびに、同じ値が何回か得られる可能性があります.彼は等概分布取得ですが、前後の取得値が異なることは保証できません.前後の2回はその分布に関連していないからです.B、エンジン、ループを定義する前にstaticは関数呼び出しが生命を終了しないことを示し、同様に私たちが呼び出すたびに前回の状態を継続して、新しいシーケンスを生成します.この時私たちは種を必要としません.
static default_random_engine e; //time()

C、分布、私達の分布はiに従って変化します
uniform_int_distribution<unsigned> u(i, sz-1);

D、要求:この数行の乱数で生成されたコードを手当たり次第に書くことができるようにするには、単語は少し長いが、覚えなければならない.また、分布はintなどのタイプを変更することができる.
貯水池アルゴリズムは,乱数生成にも用いられるhttp://blog.csdn.net/bestzem/article/details/52291953
class Solution {
public:
    Solution(vector<int> nums):org(nums) {

    }

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

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int sz=org.size();
        vector<int> deal{org};
        static default_random_engine e; //time()
        for(int i=0;iunsigned> u(i, sz-1);
            unsigned int m = u(e);  
            if(m!=i)
            {
                swap(deal[i],deal[m]);
            }
        }
        return deal;
    }
private:
    vector<int> org;
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * vector param_1 = obj.reset();
 * vector param_2 = obj.shuffle();
 */