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

Difficulty: interview

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):
         """
         :type nums: List[int]
         """
         self.nums = nums
         self.length = len(self.nums)
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         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
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         return random.choice([i for i, v in enumerate(self.nums) if v == target])
         
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums;
         
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         indices = [i for i, x in enumerate(self.nums) if x == target]
         return random.choice(indices)
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         import random
         # if only one element
         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
                 else:
                     if random.randint(0, idx) == 0:
                         ans = i
                 idx += 1
         return ans
         
         # result = -1
         # index = 0
         # for i in range(0, len(self.nums), 1):
         #     if self.nums[i] == target:
         #         if result == -1:
         #             result = i
         #         else:
         #             if random.randint(0, index) == 0:
         #                 result = i
         #         index += 1
         # return result
         
         
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         import random
         
         ans = -1
         idx = 0
         for i, num in enumerate(self.nums):
             if num == target:
                 if ans == -1:
                     ans = i
                 else:
                     if random.randint(0, idx) == 0:
                         ans = i
                 idx += 1
         return ans
         
         
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         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
                     
         
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         self.nums = nums
         self.length = len(nums)
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         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
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)


import random
 
 class Solution:
 
     def __init__(self, nums):
         """
         :type nums: List[int]
         """
         
         self.nums = nums
         
 
     def pick(self, target):
         """
         :type target: int
         :rtype: int
         """
         
         result = None
         seen = 0
         
         for i, num in enumerate(self.nums):
             
             if num == target:
                 
                 if not result:
                     result = i
                 else:
                     #
                     if random.randint(0, seen) == 0:
                         result = i
                 
                 seen += 1
         
         print("saw", seen)
         
         return result
 
 
 # Your Solution object will be instantiated and called as such:
 # obj = Solution(nums)
 # param_1 = obj.pick(target)