Java LinksedList vs Map vs Default Map
version 1, linked list (TLE, which should not have);\nI wouls assume remove use O(1) time;\n\nclass Solution {\n    List<Integer> l;\n    int m, n;\n    public 
version 1, linked list (TLE, which should not have);\nI wouls assume remove use O(1) time;\n```\nclass Solution {\n    List<Integer> l;\n    int m, n;\n    public Solution(int n_rows, int n_cols) {\n        m = n_rows;\n        n = n_cols;\n        reset();\n    }\n    \n    public int[] flip() {\n        int r = new Random().nextInt(l.size());\n        int off = l.get(r);\n        l.remove(r);\n        return new int[]{off / n, off % n};\n    }\n    \n    public void reset() {\n        l = new LinkedList<>();\n        for (int i = 0; i < m * n; i++) {\n            l.add(i);\n        }\n    }\n}\n```\n\nversion 2, hashMap, fills when reset (TLE when a lot of resets);\n```\nclass Solution {\n    Map<Integer, Integer> map;\n    int m, n, sum;\n    Random rand = new Random();\n    public Solution(int n_rows, int n_cols) {\n        m = n_rows;\n        n = n_cols;\n        sum = m * n;\n        reset();\n    }\n    \n    public int[] flip() {\n        int r = rand.nextInt(map.size());\n        int off = map.get(r);\n        map.put(r, map.get(map.size() - 1));\n        map.remove(map.size() - 1);\n        return new int[]{off / n, off % n};\n    }\n    \n    public void reset() {\n        map = new HashMap<>();\n        for (int i = 0; i < sum; i++) map.put(i, i);\n    }\n}\n```\n\nversion 3, HashMap, not refill when reset, but use default value;\nRef: https://leetcode.com/problems/random-flip-matrix/discuss/154053/Java-AC-Solution-call-Least-times-of-Random.nextInt()-function\n```\nclass Solution {\n    Map<Integer, Integer> map;\n    int m, n, sum, cnt;\n    Random rand = new Random();\n    public Solution(int n_rows, int n_cols) {\n        m = n_rows;\n        n = n_cols;\n        sum = m * n;\n        reset();\n    }\n    \n    public int[] flip() {\n        int r = rand.nextInt(cnt--);\n        int off = map.getOrDefault(r, r);\n        map.put(r, map.getOrDefault(cnt, cnt));\n        return new int[]{off / n, off % n};\n    }\n    \n    public void reset() {\n        map = new HashMap<>();\n        cnt = sum;\n    }\n}\n```\n
[]