Last updated on July 18th, 2024 at 03:43 am
Here, We see Random Pick Index LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.
List of all LeetCode Solution
Topics
Reservoir Sampling
Companies
Level of Question
Medium
![Random Pick Index LeetCode Solution](https://i0.wp.com/totheinnovation.com/wp-content/uploads/2024/02/LeetCode-Problem-Solution.png?resize=200%2C200&ssl=1)
Random Pick Index LeetCode Solution
Table of Contents
Problem Statement
Given an integer array nums
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.
Implement the Solution
class:
Solution(int[] nums)
Initializes the object with the arraynums
.int pick(int target)
Picks a random indexi
fromnums
wherenums[i] == target
. If there are multiple valid i’s, then each index should have an equal probability of returning.
Example 1:
Input [“Solution”, “pick”, “pick”, “pick”] [[[1, 2, 3, 3, 3]], [3], [1], [3]]
Output [null, 4, 0, 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.
1. Random Pick Index LeetCode Solution C++
class Solution { public: unordered_map<int,vector<int>> m; Solution(vector<int>& nums) { for(int i=0;i<nums.size();i++) { m[nums[i]].push_back(i); } } int pick(int target) { int x=m[target].size(); x=rand()%x; return m[target][x]; } };
2. Random Pick Index LeetCode Solution Java
class Solution { int[] nums; Random random; public Solution(int[] nums) { this.nums = nums; this.random = new Random(); } public int pick(int target) { int idx = -1; int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == target) { count++; if (random.nextInt(count) == 0) { idx = i; } } } return idx; } }
3. Random Pick Index Solution JavaScript
var Solution = function(nums) { this.nums = nums; this.len = nums.length; }; Solution.prototype.pick = function(target) { if (this.len == 1) return 0; var result = 0; var count = 0; for (var i = 0; i < this.len; i++) { if (this.nums[i] == target) { if (Math.floor(Math.random() * (++count)) == 0) result = i; } } return result; };
4. Random Pick Index Solution Python
class Solution(object): def __init__(self, nums): self.indices = defaultdict(list) for i, num in enumerate(nums): self.indices[num].append(i) def pick(self, target): return random.choice(self.indices[target])