O(n) to pre-process and O(1) to pick


  • 0
    S
    Random random = new Random();
    Map<Integer, List<Integer>> map = new HashMap<>();
    
    public Solution(int[] nums) {
        for (int i = 0; i < nums.length; i++)
            map.computeIfAbsent(nums[i], k -> new ArrayList<>(4)).add(i);
    }
    
    public int pick(int target) {
        List<Integer> integers = map.get(target);
        return integers.get(random.nextInt(integers.size()));
    }

  • 0
    Z

    @snap_dragon This will get following error:
    Submission Result: Memory Limit Exceeded More Details

    Last executed input:
    ["Solution","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pick","pic....


  • 0
    S

    @zsll I was waiting for OJ to add an input to fail my code but surprisingly I tried again and got accepted.

    See my last accepted submissions https://leetcode.com/snap_dragon/


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.