leetcode 384. Shuffle an Array 数组随机洗牌

缺乏、安全感 2022-06-07 02:51 210阅读 0赞

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

网上看到的代码，就这么吧！

代码如下：

public class Solution {
        
    
        private int[] nums = null;
        private Random random = null;
    
        public Solution(int[] nums) {
            this.nums = nums;
            random = new Random();
        }
    
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            return nums;
        }
    
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            if(nums == null) return null;
            int[] a = (int[])nums.clone();
            for(int i = 1; i < nums.length; i++){
                int j = random.nextInt(i + 1);
                swap(a, i, j);
            }
            return a;
        }
    
        private void swap(int[] a, int i, int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * Solution obj = new Solution(nums);
     * int[] param_1 = obj.reset();
     * int[] param_2 = obj.shuffle();
     */

下面是C++的做法

这道题让我们给数组洗牌，也就是随机打乱顺序，那么由于之前那道题[leetcode 382. Linked List Random Node 等概率随机获取结点 + 蓄水池算法][leetcode 382. Linked List Random Node _ _]我们接触到了水塘抽样的思想，这道题实际上这道题也是用类似的思路，我们遍历数组每个位置，每次都随机生成一个坐标位置，然后交换当前遍历位置和随机生成的坐标位置的数字，这样如果数组有n个数字，那么我们也随机交换了n组位置，从而达到了洗牌的目的，这里需要注意的是i + rand() % (res.size() - i)不能写成rand() % res.size()，虽然也能通过OJ，但是根据这个帖子的最后部分的概率图表，前面那种写法不是真正的随机分布，应该使用Knuth shuffle算法，感谢热心网友们的留言，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        vector<int> v;
        Solution(vector<int> nums) 
        {
            v = nums;
        }
    
        /** 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 = 0; i < res.size(); i++)
            {
                int t = i + rand() % (res.size() - i);
                swap(res[i], res[t]);
            }
            return res;
        }
    };
    
    /**
    * Your Solution object will be instantiated and called as such:
    * Solution obj = new Solution(nums);
    * vector<int> param_1 = obj.reset();
    * vector<int> param_2 = obj.shuffle();
    */

[leetcode 382. Linked List Random Node _ _]: http://blog.csdn.net/jackzhang_123/article/details/78174383