[LeetCode]Random Flip Matrix

这道题显然不可能每次O(N)去生成random，这样太耗费时间。我们可以参考Insert Delete GetRandom O(1)的方法，每一次把取了的和末尾换即可。当然这里我们并不会维护整个区间的数组，我们只需要对每一个取了的数组，重新map到结尾还没有取的数即可。每次和结尾交换的数，可能本身其已经map到了另一个数，注意这种情况即可。每次生成random的时间复杂度为O(1)，代码如下：


这道题还有另外一种方法，用sqrt decomposition切分区间。这样我们每次generate random的时间复杂度可以降到O(sqrt(N))，代码如下：