1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
// 398. Random Pick Index
#include "leetcode.h"
/*
* given an integer array 'nums' with possible duplicates, randomly output the
* index of a given 'target' numbber. you can assume that the given target
* number must exist in the array. implement the 'Solution' class: 'Solution(int
* [] nums)' initiliases 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
*/
typedef struct {
int *nums;
int numsSize;
} Solution;
Solution *solutionCreate(int *nums, int numsSize) {
size_t arr_size = numsSize * sizeof(int);
Solution *obj = (Solution *)malloc(sizeof(*obj));
obj->nums = (int *)malloc(arr_size);
obj->numsSize = numsSize;
memcpy(obj->nums, nums, arr_size);
return obj;
}
int solutionPick(Solution *obj, int target) {
int cnt = 0, res = -1;
for (int i = 0; i < obj->numsSize; i++)
if (obj->nums[i] == target) {
cnt++;
if (!(rand() % cnt))
res = i;
}
return res;
}
void solutionFree(Solution *obj) {
free(obj->nums);
free(obj);
}
int main() {
int nums[] = {1, 2, 3, 3, 3, 3};
Solution *obj = solutionCreate(nums, ARRAY_SIZE(nums));
printf("%d\n", solutionPick(obj, 3)); // expect: 4
printf("%d\n", solutionPick(obj, 1)); // expect: 0
printf("%d\n", solutionPick(obj, 3)); // expect: 2
}
|