LeetCode. 519 随机翻转矩阵

519. 随机翻转矩阵

解题思路：

​ 算法整体主要考察了二维数组的Random洗牌方法，核心思路是将二维数组转换为一维数组，用一维数组的洗牌算法思路来解决。

​ 我们可以联系到一般的洗牌方法：假设数组的元素个数为count，则我们从0~count-1随机取任意一个数，将该数作为索引在数组中对应元素与最后一个元素进行交换，并且返回该元素作为当前随机抽选到的数，这样可以保证每次取值都不重复，且当循环count次后可以达到洗牌的效果。

​ 得到基本思路后，我们可以通过两种方法来实现：

• 模拟整个的洗牌过程，初始化一个数组，其索引对应真实值（对应二维数组），每次取到真实值与最后一个元素进行交换，重复过程

  根据思路得到的代码：

  class Solution {
  private:
      int _m,_n,_count;
      int *arr;
  public:
      //MARKER:类似于洗牌算法的一种思路
      Solution(int m, int n) {
          _m=m;_n=n;_count=m*n;
          arr=new int[_count];
          //初始化数组
          for(int i=0;i<_count;i++){
              arr[i]=i;
          }
      }
      
      vector<int> flip() {
          int ran=rand()%_count--;
          int index=arr[ran];
          swap(ran,_count);
  
          return {index/_n,index%_n};
      }
      
      void reset() {
          _count=_m*_n;
  
          //重新初始化数组
          for(int i=0;i<_count;i++){
              arr[i]=i;
          }
      }
  
      void swap(int n,int m){
          int temp=arr[n];
          arr[n]=arr[m];
          arr[m]=temp;
      }
      
  };

  结果是超时了。。

• 用哈希表代替每次的交换过程，每次random过后得到索引ran，用通过哈希表取到ran对应的真实值index，并且将[ran,GetOrDefault(_count,_count)]在哈希表中添加或修改。

  挺巧妙的一种方法：

  class Solution {
  private:
      int _m,_n,_count;
      map<int,int> m;
  public:
      //MARKER:类似于洗牌算法的一种思路
      Solution(int m, int n) {
          _m=m;_n=n;_count=m*n;
      }
      
      vector<int> flip() {
          int ran=rand()%_count--;
          int index=GetOrDefault(ran,ran);
          m[ran] = GetOrDefault(_count, _count); //相当于被抽到的元素与最后一个元素交换
          return {index/_n,index%_n};
      }
      
      void reset() {
          _count=_m*_n;
          m.clear();
      }
  
      //实现C++的getOrDefault()
      int GetOrDefault(int index,int defaultNum){
          return this->m.count(index)==1?m[index]:defaultNum;
      }
  };

  时间复杂度得到了优化

写的时候遇到的一些坑：

• map.insert()在已有对应元素的情况不会去修改对应索引的元素值，一开始用insert写代码思路都没错却不知道为什么没过，后来才发现这个情况。
• m[ran]的赋值必须为GetOrDefault(_count,_count)而非_count,因为在总体范围遍历到_count之前，_count的值可能在之前的遍历中就被随机到并赋值为了之前遍历过程的最后一个元素，因此这里得通过哈希表来获取到实际值。

​ 最后写着写着发现曾经的一次面试中也被问到二维数组的随机洗牌问题，当时只想到了第一种转换为一维数组并交换的方法，如今算是摸索到了更好的思路（哈希表存储）