Сложность: medium
Из целочисленного массива nums с возможными дубликатами случайным образом выведите индекс заданного целевого числа. Можно предположить, что заданное целевое число должно существовать в массиве. Реализация класса Solution: Solution(int[] nums) Инициализирует объект с массивом nums. int pick(int target) Выбирает случайный индекс i из nums, где nums[i] == target. Если существует несколько допустимых i, то каждый индекс должен иметь равную вероятность возврата.
Пример:
Input
["Solution", "pick", "pick", "pick"]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output
[null, 4, 0, 2]
👨💻 Алгоритм:
1⃣Инициализируйте объект с массивом nums. Сохраните этот массив для дальнейшего использования.
2⃣Реализуйте метод pick(target), который выбирает случайный индекс i из массива nums, где nums[i] равен target. Если таких индексов несколько, каждый из них должен иметь равную вероятность быть выбранным.
3⃣Для реализации метода pick используйте алгоритм reservoir sampling для выбора случайного индекса.
😎 Решение:
import random
class Solution:
def __init__(self, nums: List[int]):
self.nums = nums
def pick(self, target: int) -> int:
count = 0
result = -1
for i, num in enumerate(self.nums):
if num == target:
count += 1
if random.randint(1, count) == count:
result = i
return result
Ставь 👍 и забирай 📚 Базу знаний