Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note:
The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:


int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

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

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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Mathematics

Probability

Starter 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)

Solutions:
class Solution:

	def __init__(self, nums):
		self.nums = nums
		self.length = len(self.nums)

	def pick(self, target):
		first_idx = None
		idx_count = 0
		for i in range(self.length):
			if self.nums[i] == target:
				if first_idx is None:
					first_idx = i
				idx_count += 1
			elif first_idx is not None:
				break
		if idx_count > 0:
			return int(idx_count * random.random() // 1) + first_idx


class Solution:

	def __init__(self, nums):
		self.nums = nums

	def pick(self, target):
		return random.choice([i for (i, v) in enumerate(self.nums) if v == target])


class Solution:

	def __init__(self, nums):
		self.nums = nums

	def pick(self, target):
		indices = [i for (i, x) in enumerate(self.nums) if x == target]
		return random.choice(indices)


class Solution:

	def __init__(self, nums):
		self.nums = nums

	def pick(self, target):
		import random
		if len(self.nums) == 1:
			return 0
		ans = -1
		idx = 0
		for (i, num) in enumerate(self.nums):
			if num == target:
				if ans == -1:
					ans = i
				elif random.randint(0, idx) == 0:
					ans = i
				idx += 1
		return ans


class Solution:

	def __init__(self, nums):
		self.nums = nums

	def pick(self, target):
		res = None
		ct = 0
		for (i, x) in enumerate(self.nums):
			if x == target:
				ct += 1
				pb = random.randint(1, ct)
				if pb == ct:
					res = i
		return res


class Solution:

	def __init__(self, nums):
		self.nums = nums
		self.length = len(nums)

	def pick(self, target):
		(result, index) = (self.nums.index(target), 1)
		for i in range(self.length):
			num = self.nums[i]
			if num == target and random.randint(0, index) is 0:
				result = i
				index += 1
		return result