leetcode 519. Random Flip Matrix | 519. 随机翻转矩阵（洗牌算法Fisher–Yates shuffle）

r囧r小猫 2022-09-12 04:53 43阅读 0赞

## 题目 ##

[https://leetcode.com/problems/random-flip-matrix/][https_leetcode.com_problems_random-flip-matrix]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

看了答案：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16 1]

#### 洗牌算法 Fisher–Yates shuffle ####

Fisher–Yates shuffle 算法是高效和等概率的一个洗牌算法。其核心思想是从1到n之间随机出一个数和最后一个数(n)交换，然后从1到n-1之间随机出一个数和倒数第二个数(n-1)交换…

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

class Solution { 
        Map<Integer, Integer> map;
        int size, m, n;
        Random rand;
    
        public Solution(int m, int n) { 
            map = new HashMap<>();
            size = m * n;
            this.m = m;
            this.n = n;
            rand = new Random();
        }
    
        public int[] flip() { 
            int r = rand.nextInt(size--);
            int i = map.getOrDefault(r, r);
            map.put(r, map.getOrDefault(size, size));
            return new int[]{ i / n, i % n};
        }
    
        public void reset() { 
            map.clear();
            size = this.m * this.n;
        }
    }
    
    /** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(m, n); * int[] param_1 = obj.flip(); * obj.reset(); */

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16 2]

[https_leetcode.com_problems_random-flip-matrix]: https://leetcode.com/problems/random-flip-matrix/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c2bf09aa0e4f4521ab7d012a77182b7c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9e3d8c8097a24673865f1d7c060b2aca.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/f98ee6502e964641b0a7ed7011f88d89.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/3a9bc7e903154961b56de833b938ce00.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_2_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/b09e4506763a4d8c9b74e7844b2e1e67.png