1. 题目描述

problem link

Given an array of integers 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.

Note:

The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

2. 解题

首先了解蓄水池采样算法

很明显可以用蓄水池采样算法解决这个问题，代码如下：

typedef struct {
    int* nums;
    int numsSize;
} Solution;


Solution* solutionCreate(int* nums, int numsSize) {
    Solution* sl = (Solution *)malloc(sizeof(Solution));
    sl->nums = nums;
    sl->numsSize = numsSize;
    srand((unsigned int)time(NULL));

    return sl;
}

int solutionPick(Solution* obj, int target) {
    int res, tmp;
    int count = 1;

    int index = 0;
    while (index < obj->numsSize) {
        if (obj->nums[index] == target) {
            tmp = rand() % count;
            if (tmp == 0) {
                res = index;
            }
            count++;
        }
        index++;
    }
    
    return res;
}

void solutionFree(Solution* obj) {
    free(obj);
}