Leetcode Random Pick Index problem solution

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.

Leetcode Random Pick Index problem solution

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

coding problems