LeetCode刷题之洗牌算法

LeetCode刷题之洗牌算法

1.洗牌算法的思路

共有 n 个不同的数,根据每个位置能够选择什么数,共有 n! 种组合。

题目要求每次调用 shuffle 时等概率返回某个方案,或者说每个元素都够等概率出现在每个位置中。

我们可以使用 Knuth 洗牌算法,在 O(n) 复杂度内等概率返回某个方案。

具体的,我们从前往后尝试填充 [0, n - 1][0,n−1] 该填入什么数时,通过随机当前下标与(剩余的)哪个下标进行值交换来实现。

对于下标 x 而言,我们从 [x, n - 1][x,n−1] 中随机出一个位置与 x 进行值交换,当所有位置都进行这样的处理后,我们便得到了一个公平的洗牌方案。

对于下标为 00 位置,从 [0, n - 1][0,n−1] 随机一个位置进行交换,共有 nn 种选择;下标为 11 的位置,从 [1, n - 1][1,n−1] 随机一个位置进行交换,共有 n - 1n−1 种选择 ... 且每个位置的随机位置交换过程相互独立。

2.具体题目

2.1 LeetCode之384打乱数组

  • 代码实现

  • /*
     * @lc app=leetcode.cn id=384 lang=cpp
     *
     * [384] 打乱数组
     */
    
    // @lc code=start
    class Solution {
    public:
        Solution(vector<int>& nums) {
            int len = nums.size();
            l = len;
            for (int i = 0; i < len; i++) {
               num.push_back(nums[i]);
               ass.push_back(nums[i]);
            }
        }
        
        vector<int> reset() {
            return ass;
        }
        
        vector<int> shuffle() {
            for(int i=0; i<l-1; i++) {
                int r = rand() % (l-i) + i;
    
                int temp = num[i];
                num[i] = num[r];
                num[r] = temp;
            }
            return num;
        }
    
    private:
        int l;
        vector<int> num;
        vector<int> ass;
    };
    
    /**
     * 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();
     */
    // @lc code=end
    
上一篇:leetcode_26:删除有序数组中的重复项:Java


下一篇:26 删除有序数组中的重复项