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は関数呼び出しが生命を終了しないことを示し、同様に私たちが呼び出すたびに前回の状態を継続して、新しいシーケンスを生成します.この時私たちは種を必要としません.
C、分布、私達の分布はiに従って変化します
D、要求:この数行の乱数で生成されたコードを手当たり次第に書くことができるようにするには、単語は少し長いが、覚えなければならない.また、分布はintなどのタイプを変更することができる.
貯水池アルゴリズムは,乱数生成にも用いられるhttp://blog.csdn.net/bestzem/article/details/52291953
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();
*/