#398

Random Pick Index

specialist · 705 · lc medium +30 · 65% accepted · 1,392 likes · top 69%

Description

An integer array nums may contain duplicate values. Build a data structure that, given any target guaranteed to appear in nums, returns one of the positions where target occurs with equal probability for each occurrence.

Implement the Solution class:

- Solution(int[] nums) Constructs the object from array nums.

- int pick(int target) Returns a uniformly random index i satisfying nums[i] == target.

Example 1:

Input

["Solution", "pick", "pick", "pick"]

[[[1, 2, 3, 3, 3]], [3], [1], [3]]

Output

[null, 4, 0, 2]

Example 2:

Explanation

Solution solution = new Solution([1, 2, 3, 3, 3]);

solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

solution.pick(1); // It should return 0. Since in the array only nums[0] is equal to 1.

solution.pick(3); // It should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.

Code

class Solution:

    def __init__(self, nums: List[int]):
        

    def pick(self, target: int) -> int:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)

class Solution:

    def __init__(self, nums: List[int]):
        

    def pick(self, target: int) -> int:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(nums)
# param_1 = obj.pick(target)