leetcode 力扣 913 随机翻转矩阵题解 算法题.docx
- 文档编号:10888373
- 上传时间:2023-05-28
- 格式:DOCX
- 页数:23
- 大小:20.32KB
leetcode 力扣 913 随机翻转矩阵题解 算法题.docx
《leetcode 力扣 913 随机翻转矩阵题解 算法题.docx》由会员分享,可在线阅读,更多相关《leetcode 力扣 913 随机翻转矩阵题解 算法题.docx(23页珍藏版)》请在冰点文库上搜索。
leetcode力扣913随机翻转矩阵题解算法题
题目:
随机翻转矩阵
给你一个mxn的二元矩阵matrix,且所有值被初始化为0。
请你设计一个算法,随机选取一个满足 matrix[i][j]==0的下标 (i,j),并将它的值变为1。
所有满足matrix[i][j]==0的下标(i,j)被选取的概率应当均等。
尽量最少调用内置的随机函数,并且优化时间和空间复杂度。
实现Solution类:
•Solution(intm,intn)使用二元矩阵的大小m和n初始化该对象
•int[]flip()返回一个满足 matrix[i][j]==0的随机下标[i,j],并将其对应格子中的值变为1
•voidreset()将矩阵中所有的值重置为0
示例:
输入
["Solution","flip","flip","flip","reset","flip"]
[[3,1],[],[],[],[],[]]
输出
[null,[1,0],[2,0],[0,0],null,[2,0]]
解释
Solutionsolution=newSolution(3,1);
solution.flip();//返回[1,0],此时返回[0,0]、[1,0]和[2,0]的概率应当相同
solution.flip();//返回[2,0],因为[1,0]已经返回过了,此时返回[2,0]和[0,0]的概率应当相同
solution.flip();//返回[0,0],根据前面已经返回过的下标,此时只能返回[0,0]
solution.reset();//所有值都重置为0,并可以再次选择下标返回
solution.flip();//返回[2,0],此时返回[0,0]、[1,0]和[2,0]的概率应当相同
提示:
•1<=m,n<=104
•每次调用flip时,矩阵中至少存在一个值为0的格子。
•最多调用1000次flip和reset方法。
语言:
Java
classSolution{
Map
intm,n,total;
Randomrand=newRandom();
publicSolution(intm,intn){
this.m=m;
this.n=n;
this.total=m*n;
}
publicint[]flip(){
intx=rand.nextInt(total);
total--;
//查找位置x对应的映射
intidx=map.getOrDefault(x,x);
//将位置x对应的映射设置为位置total对应的映射
map.put(x,map.getOrDefault(total,total));
returnnewint[]{idx/n,idx%n};
}
publicvoidreset(){
total=m*n;
map.clear();
}
}
语言:
Java
classSolution{
intm,n;
inttotal,bucketSize;
List
Randomrand=newRandom();
publicSolution(intm,intn){
this.m=m;
this.n=n;
this.total=m*n;
this.bucketSize=(int)Math.sqrt(total);
for(inti=0;i buckets.add(newHashSet } } publicint[]flip(){ intx=rand.nextInt(total); intsumZero=0; intcurr=0; total--; for(Set buckets){ if(sumZero+bucketSize-bucket.size()>x){ for(inti=0;i if(! bucket.contains(curr+i)){ if(sumZero==x){ bucket.add(curr+i); returnnewint[]{(curr+i)/n,(curr+i)%n}; } sumZero++; } } } curr+=bucketSize; sumZero+=bucketSize-bucket.size(); } returnnull; } publicvoidreset(){ total=m*n; for(Set buckets){ bucket.clear(); } } } 语言: Java classSolution{ intm,n; Set Randomrandom=newRandom(300); publicSolution(int_m,int_n){ m=_m;n=_n; } publicint[]flip(){ inta=random.nextInt(m*n),b=a; while(a>=0&&set.contains(a))a--; while(b intc=a>=0&&! set.contains(a)? a: b; set.add(c); returnnewint[]{c/n,c%n}; } publicvoidreset(){ set.clear(); } } 语言: C++ classSolution{ public: Solution(intm,intn){ this->m=m; this->n=n; this->total=m*n; srand(time(nullptr)); } vector intx=rand()%total; vector total--; //查找位置x对应的映射 if(map.count(x)){ ans={map[x]/n,map[x]%n}; }else{ ans={x/n,x%n}; } //将位置x对应的映射设置为位置total对应的映射 if(map.count(total)){ map[x]=map[total]; }else{ map[x]=total; } returnans; } voidreset(){ total=m*n; map.clear(); } private: intm; intn; inttotal; unordered_map }; 语言: C++ classSolution{ public: Solution(intm,intn){ this->m=m; this->n=n; total=m*n; bucketSize=sqrt(m*n); for(inti=0;i buckets.push_back({}); } srand(time(nullptr)); } vector intx=rand()%total; intsumZero=0; intcurr=0; total--; for(auto&bucket: buckets){ if(sumZero+bucketSize-bucket.size()>x){ for(inti=0;i if(! bucket.count(curr+i)){ if(sumZero==x){ bucket.emplace(curr+i); return{(curr+i)/n,(curr+i)%n}; } sumZero++; } } } curr+=bucketSize; sumZero+=bucketSize-bucket.size(); } return{}; } voidreset(){ for(auto&bucket: buckets){ bucket.clear(); } total=m*n; } private: intm; intn; intbucketSize; inttotal; vector }; 语言: C++ classSolution{ intr,c,k;//r: 矩阵的行数,c: 列数,k: 矩阵中元素的个数 unordered_map x->x,默认用这个映射,将不满足这个映射的特殊键值对存入哈希表 public: Solution(intm,intn){ r=m; c=n; k=r*c; } vector intkey=rand()%k; intval=key;//默认的映射规则: x->x(x的范围是: 0->k-1) if(dict.count(key)) val=dict[key]; if(dict.count(k-1))//当key处的kvp用过后,用最后一个kvp(key=k-1)覆盖之,然后删掉最后一个kvp,就可以在剩下的数中实现随机化选择 { dict[key]=dict[k-1]; dict.erase(k-1); } else dict[key]=k-1; k--;//表示删掉了末尾的一个数 intnewRow=val/c; intnewCol=val%c; return{newRow,newCol}; } voidreset(){ k=r*c; dict.clear(); } }; 语言: C publicclassSolution{ Dictionary intm,n,total; Randomrand=newRandom(); publicSolution(intm,intn){ this.m=m; this.n=n; this.total=m*n; } publicint[]Flip(){ intx=rand.Next(total); total--; //查找位置x对应的映射 intidx=dictionary.ContainsKey(x)? dictionary[x]: x; //将位置x对应的映射设置为位置total对应的映射 intvalue=dictionary.ContainsKey(total)? dictionary[total]: total; if(dictionary.ContainsKey(x)){ dictionary[x]=value; }else{ dictionary.Add(x,value); } returnnewint[]{idx/n,idx%n}; } publicvoidReset(){ total=m*n; dictionary.Clear(); } } 语言: C publicclassSolution{ intm,n; inttotal,bucketSize; IList Randomrand=newRandom(); publicSolution(intm,intn){ this.m=m; this.n=n; this.total=m*n; this.bucketSize=(int)Math.Sqrt(total); for(inti=0;i buckets.Add(newHashSet } } publicint[]Flip(){ intx=rand.Next(total); intsumZero=0; intcurr=0; total--; foreach(ISet if(sumZero+bucketSize-bucket.Count>x){ for(inti=0;i if(! bucket.Contains(curr+i)){ if(sumZero==x){ bucket.Add(curr+i); returnnewint[]{(curr+i)/n,(curr+i)%n}; } sumZero++; } } } curr+=bucketSize; sumZero+=bucketSize-bucket.Count; } returnnull; } publicvoidReset(){ total=m*n; foreach(ISet bucket.Clear(); } } } 语言: Python classSolution: def__init__(self,m: int,n: int): self.m=m self.n=n self.total=m*n self.map={} defflip(self)->List[int]: x=random.randint(0,self.total-1) self.total-=1 #查找位置x对应的映射 idx=self.map.get(x,x) #将位置x对应的映射设置为位置total对应的映射 self.map[x]=self.map.get(self.total,self.total) return[idx//self.n,idx%self.n] defreset(self)->None: self.total=self.m*self.n self.map.clear() 语言: Python classSolution: def__init__(self,m: int,n: int): self.m,self.n=m,n self.total=m*n self.bucketSize=math.floor(math.sqrt(m*n)) self.buckets=[set()for_inrange(0,self.total,self.bucketSize)] defflip(self)->List[int]: x=random.randint(0,self.total-1) self.total-=1 sumZero=0 curr=0 foriinrange(len(self.buckets)): ifsumZero+self.bucketSize-len(self.buckets[i])>x: forjinrange(self.bucketSize): if(curr+j)notinself.buckets[i]: ifsumZero==x: self.buckets[i].add(curr+j) return[(curr+j)//self.n,(curr+j)%self.n] sumZero+=1 curr+=self.bucketSize sumZero+=self.bucketSize-len(self.buckets[i]) return[] defreset(self)->None: self.total=self.m*self.n foriinrange(len(self.buckets)): self.buckets[i].clear() 语言: JavaScript varSolution=function(m,n){ this.m=m; this.n=n; this.total=m*n; this.map=newMap(); }; Solution.prototype.flip=function(){ constx=Math.floor(Math.random()*this.total); this.total--; //查找位置x对应的映射 constidx=this.map.get(x)||x; //将位置x对应的映射设置为位置total对应的映射 this.map.set(x,this.map.get(this.total)||this.total); return[Math.floor(idx/this.n),idx%this.n]; }; Solution.prototype.reset=function(){ this.total=this.m*this.n; this.map.clear(); }; 语言: JavaScript varSolution=function(m,n){ this.m=m; this.n=n; this.total=m*n; this.bucketSize=Math.floor(Math.sqrt(this.total)); this.buckets=[]; for(leti=0;i this.buckets.push(newSet()); } }; Solution.prototype.flip=function(){ constx=Math.floor(Math.random()*this.total); letsumZero=0; letcurr=0; this.total--; for(constbucketofthis.buckets){ if(sumZero+this.bucketSize-bucket.size>x){ for(leti=0;i if(! bucket.has(curr+i)){ if(sumZero===x){ bucket.add(curr+i); return[Math.floor((curr+i)/this.n),(curr+i)%this.n]; } sumZero++; } } } curr+=this.bucketSize; sumZero+=this.bucketSize-bucket.size; } returnundefined; }; Solution.prototype.reset=function(){ this.total=this.m*this.n; for(constbucketofthis.buckets){ bucket.clear(); } }; 语言: JavaScript /** *@param{number}m *@param{number}n */ varSolution=function(m,n){ this.m=m this.n=n this.total=m*n-1 this.map=newMap() }; /** *@return{number[]} */ Solution.prototype.flip=function(){ constr=Math.floor(Math.random()*(this.total+1)) constidx=this.map.has(r)? this.map.get(r): r th
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- leetcode 力扣 913 随机翻转矩阵 题解 算法题 随机 翻转 矩阵 算法