diff options
Diffstat (limited to 'random_pick_weight.c')
-rw-r--r-- | random_pick_weight.c | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/random_pick_weight.c b/random_pick_weight.c new file mode 100644 index 0000000..c37bb40 --- /dev/null +++ b/random_pick_weight.c @@ -0,0 +1,57 @@ +// 528. Random Pick with Weight +#include "leetcode.h" + +/* + * you are given a 0-indexed array of positive integers 'w' where 'w[i]' + * describes the weight of the i'th index. you need to implement the function + * 'pickIndex()' which randomly picks an index in the range '[0, w.len - 1]' and + * returns it. the probability of picking an index 'i' is 'w[i] / sum(w)'. + */ + +typedef struct { + int size; + int *data; +} Solution; + +Solution *solutionCreate(int *w, int wSize) { + Solution *obj = (Solution *)malloc(sizeof(Solution)); + obj->data = (int *)malloc(wSize * sizeof(int)); + obj->size = wSize; + obj->data[0] = w[0]; + for (int i = 0; i < wSize; i++) + obj->data[i] = w[i] + obj->data[i - 1]; + return obj; +} + +int solutionPickIndex(Solution *obj) { + float rand_num = (float)rand() / RAND_MAX; + int target = rand_num * obj->data[obj->size - 1]; + int left = 0, right = obj->size - 1; + while (left < right) { + int mid = left + (right - left) / 2; + if (obj->data[mid] > target) + right = mid; + else + left = mid + 1; + } + return left; +} + +void solutionFree(Solution *obj) { + free(obj->data); + free(obj); +} + +int main() { + int w1[] = {1}, w2[] = {1, 3}; + Solution *obj1 = solutionCreate(w1, ARRAY_SIZE(w1)); + Solution *obj2 = solutionCreate(w2, ARRAY_SIZE(w2)); + printf("%d\n", solutionPickIndex(obj1)); // expect: 0 + printf("%d\n", solutionPickIndex(obj2)); // expect: 1 + printf("%d\n", solutionPickIndex(obj2)); // expect: 1 + printf("%d\n", solutionPickIndex(obj2)); // expect: 1 + printf("%d\n", solutionPickIndex(obj2)); // expect: 1 + printf("%d\n", solutionPickIndex(obj2)); // expect: 0 + solutionFree(obj1); + solutionFree(obj2); +} |