398. 随机数索引-哈希表法

398. 随机数索引

给你一个可能含有 重复元素 的整数数组 nums ，请你随机输出给定的目标数字 target 的索引。你可以假设给定的数字一定存在于数组中。

实现 Solution 类：

Solution(int[] nums) 用数组 nums 初始化对象。
int pick(int target) 从 nums 中选出一个满足 nums[i] == target 的随机索引 i 。如果存在多个有效的索引，则每个索引的返回概率应当相等。

示例：

输入
[“Solution”, “pick”, “pick”, “pick”]
[[[1, 2, 3, 3, 3]], [3], [1], [3]]
输出
[null, 4, 0, 2]

解释
Solution solution = new Solution([1, 2, 3, 3, 3]);
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。
solution.pick(1); // 返回 0 。因为只有 nums[0] 等于 1 。
solution.pick(3); // 随机返回索引 2, 3 或者 4 之一。每个索引的返回概率应该相等。

解题代码如下：

typedef struct {
    
     long long index; 
    long long val;
    struct Solution *next;

} Solution;



Solution* solutionCreate(int* nums, int numsSize) {
    
    Solution *l=(Solution *)malloc(sizeof(Solution)*10000);
    int i;
    for(i=0;i<10000;i++){
    
        (l+i)->next=NULL;
    }
    for(i=0;i<numsSize;i++){
    
        Solution *p=(Solution *)malloc(sizeof(Solution));
        p->index=i;
        p->val=nums[i];
        p->next=(l+abs(nums[i])%10000)->next;
        (l+abs(nums[i])%10000)->next=p;
    }
    return l;

}

int solutionPick(Solution* obj, int target) {
    
     Solution * p=(obj+abs(target)%10000)->next; 
     int count=0;
     int pc=rand();
    while(p){
    
        if(p->val==target){
    
            count++;
        }
        p=p->next;
    }
    pc=pc%count;
    int cz=0;
   
    p=(obj+abs(target)%10000)->next; 

     while(p){
    
        if(p->val==target){
    
          
            if(cz==pc){
    
                return p->index;
            }
              cz++;
        }
        p=p->next;
    }

    return -1;




}

void solutionFree(Solution* obj) {
    

}

/** * Your Solution struct will be instantiated and called as such: * Solution* obj = solutionCreate(nums, numsSize); * int param_1 = solutionPick(obj, target); * solutionFree(obj); */