從N個數中隨機取一個數放在第一個位置

從剩下N-1個數中隨機取一個數放在第二個位置。

依次放完每一個數。

可以證明每個位置每個數都是等可能出現的。

可以用數學證明，也可以用遞歸解釋。

class Solution {

public:

vector original_nums;

vector current_nums;

Solution(vector& nums) {

original_nums = nums;

current_nums = nums;

}

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

vector reset() {

return original_nums;

}

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

vector shuffle() {

int n = current_nums.size();

for(int i=0;i

swap(current_nums[i],current_nums[random()%(n-i)]);

}

return current_nums;

}

};

/**

* 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();

*/

總結

以上是生活随笔為你收集整理的Java打乱牌的算法_Leetcode 384. 打乱数组 (洗牌算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。