LeetCode Top Interview Questions 384. Shuffle an Array (Java版; Meidum)

桃扇骨 2023-07-03 02:35 71阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 384. Shuffle an Array (Java版; Meidum) ##

#### 题目描述 ####

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

#### 第一次做; 主要是弄明白下面题解中洗牌算法的本质: 如果有n张牌, 那么洗牌的结果应该是等可能的n!种 采用交换的方式进行洗牌的算法貌似叫做Fisher-Yates算法, 有四种写法, 看下面的题解; 注意生成随机整数的方法, 可以使用rand.nextInt(max - min) + min;这种写法获取\[a,b)区间上的随机整数 ####

class Solution { 
        private Random random;
        int[] ori;
        int[] nums;
        public Solution(int[] nums) { 
            ori = Arrays.copyOf(nums, nums.length);
            random = new Random();
            this.nums = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() { 
            nums = Arrays.copyOf(ori, ori.length);
            return nums;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() { 
            //洗牌算法, 牢记:n张牌的洗牌结果应该有n!种, 每种结果都是等可能
            int n = nums.length;
            for(int i=n-1; i>=0; i--){ 
                int index = random.nextInt(i+1);
                swap(nums, i, index);
            }
            return nums;
        }
        
        private void swap(int[] arr, int i, int j){ 
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    
    /** * 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(); */

#### 优秀题解 ####

![format_png][]

[welcome to my blog]: https://littlehaes.com
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9ub3RlLnlvdWRhby5jb20veXdzL3B1YmxpYy9yZXNvdXJjZS8yOGE0OGE3NTE3ODJhOTRiMTQzYjUxNGI2MmQ4MjMzNC94bWxub3RlLzk5OTE4QkE1MTFDMTQxOTVBQkE4MDY4ODc1RkE5M0IyLzU2Nzg1?x-oss-process=image/format,png