519. Random Flip Matrix

• 519. Random Flip Matrix
  • Description
  • Intuition
  • Pitfall
  • Solution

Description

Here

Intuition

首先， intuitively，可以使用一个Fisher-Yeats Shuffle Algorithm产生一个随机数组

两个问题：

1. 必须用一个array事先存好
2. 每次都要重新shuffle所有

第一个问题可以用一个Map的getOrDefault来假装已经initialize了

Pitfall

Solution

private final Map<Integer, Integer> map = new HashMap<>();
  private final int rows, cols, maxCount;
  private int index;

  private final Random rand = new Random();

  public VirtualArraySolution(final int rows, final int cols) {
    this.rows = rows;
    this.cols = cols;
    maxCount = rows * cols;

    reset();
  }


  public int[] flip() {
    final int i = rand.nextInt(index--);
    int indexVal = map.getOrDefault(index, index);
    int iVal = map.getOrDefault(i, i);

    map.put(i, indexVal);
    map.put(index, iVal);
    return new int[]{iVal / cols, iVal % cols};
  }


  public void reset() {
    index = rows * cols;
  }

• Naive Solution
• Optimal Solution