leetcode384 打乱数组-洗牌算法

落日映苍穹つ 2023-06-30 09:18 12阅读 0赞

打乱一个没有重复元素的数组。

示例:

// 以数字集合 1, 2 和 3 初始化数组。  
int\[\] nums = \{1,2,3\};  
Solution solution = new Solution(nums);

// 打乱数组 \[1,2,3\] 并返回结果。任何 \[1,2,3\]的排列返回的概率应该相同。  
solution.shuffle();

// 重设数组到它的初始状态\[1,2,3\]。  
solution.reset();

// 随机返回数组\[1,2,3\]打乱后的结果。  
solution.shuffle();

首先，怎么打乱数组，却又要保证等概率随机呢？  
答案就是洗牌算法。

for (int i = 0;i < nums.length;i++) {
        
    	int random = RandomRange(i,nums.length);
    	sawp(i,ranom);
    	}

以上这段代码，就是洗牌算法的核心  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20200116183411752.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 1]  
那么就是 5! = 5 \* 4 \*3 \*2 \*1;  
那么N张牌就是N！ 就是这么简单，相信你们一看就懂。  
附上自己的代码》》》

class Solution {
        
    
        int[] original = null;
        Random random = new Random();    
        public Solution(int[] nums) {
        
            this.original = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
        
            return this.original;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
        
            int[] nums = new int[this.original.length];
            for (int i = 0;i < nums.length;i++) {
        
                nums[i] = this.original[i];
            }
            int len = nums.length;
            for (int i = 0;i < nums.length;i++) {
        
                int randoms = range(i,len);
                swap(nums,i,randoms);  
            }
            return nums;
        }
    
        int range(int min,int max) {
        
            return random.nextInt(max - min) + min;
        }
        void swap(int[] nums,int i,int j) {
        
            int temp = nums[i];
            nums[i] = nums[j];
            nums[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();
     */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200116183356421.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ==,size_16,color_FFFFFF,t_70
[20200116183411752.png]: https://img-blog.csdnimg.cn/20200116183411752.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020011618362499.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ==,size_16,color_FFFFFF,t_70