---
# System prepended metadata

title: 0384. Shuffle an Array
tags: [Leetcode, Medium, Microsoft]

---

# 0384. Shuffle an Array
###### tags: `Leetcode` `Microsoft` `Medium`
Link: https://leetcode.com/problems/shuffle-an-array/
## 思路
Fisher-Yates 洗牌算法跟暴力算法很像。
在每次迭代中，生成一个范围在当前下标到数组末尾元素下标之间的随机整数。接下来，将当前元素和随机选出的下标所指的元素互相交换 - 这一步模拟了每次从 “帽子” 里面摸一个元素的过程，其中选取下标范围的依据在于每个被摸出的元素都不可能再被摸出来了。此外还有一个需要注意的细节，当前元素是可以和它本身互相交换的 - 否则生成最后的排列组合的概率就不对了
## Code
```java=
class Solution {
    private int[] original;
    private int[] array;
    
    Random rand = new Random();
    
    private void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
    private int randomInt(int l, int r){
        return rand.nextInt(r-l)+l;
    }
    
    public Solution(int[] nums) {
        original = nums;
        array = nums.clone();
    }
    
    public int[] reset() {
        return original;
    }
    
    public int[] shuffle() {
        for(int i = 0;i < array.length;i++){
            swap(array, i, randomInt(i,array.length));
        }
        return array;
    }
}
```