In this Leetcode Random Pick Index problem solution you are 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 array nums.
- int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.
Problem solution in Python.
class Solution(object): def __init__(self, nums): """ :type nums: List[int] """ self.nums = nums def pick(self, target): count = 0 index = [] for idx, num in enumerate(self.nums): if num == target: count +=1 index.append(idx) return index[r]
Problem solution in Java.
HashMap<Integer, List<Integer>> map = new HashMap(); public Solution(int[] nums) { List<Integer> list; for(int i = 0; i<nums.length; i++){ list = map.getOrDefault(nums[i], new ArrayList<Integer>()); list.add(i); map.put(nums[i], list); list = null; } } public int pick(int target) { List<Integer> list = map.get(target); double ret = Double.valueOf(list.size()) * Math.random(); return list.get((int) ret); }
Problem solution in 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) { return m[target][rand() % m[target].size()]; } };
Problem solution in C.
#include <stdlib.h> typedef struct { int *array; int *nums; int numsSize; } Solution; Solution* solutionCreate(int* nums, int numsSize) { Solution* obj=(Solution*)malloc(sizeof(Solution)); obj->array=(int*)calloc(1000,sizeof(int)); obj->nums=nums; obj->numsSize=numsSize; return obj; } int solutionPick(Solution* obj, int target) { int count=0; for(int i=0;i<obj->numsSize;i++){ if(obj->nums[i]==target){ obj->array[count++]=i; } } if(count==1){ return obj->array[count-1]; } return obj->array[rand()%count]; } void solutionFree(Solution* obj) { free(obj); }
0 Comments