diff options
-rw-r--r-- | random_pick_index.c | 50 | ||||
-rw-r--r-- | random_pick_index.py | 40 |
2 files changed, 90 insertions, 0 deletions
diff --git a/random_pick_index.c b/random_pick_index.c new file mode 100644 index 0000000..509bc79 --- /dev/null +++ b/random_pick_index.c @@ -0,0 +1,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 +} diff --git a/random_pick_index.py b/random_pick_index.py new file mode 100644 index 0000000..e79add9 --- /dev/null +++ b/random_pick_index.py @@ -0,0 +1,40 @@ +# 398. Random Pick Index +from random import randint + +""" +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 +""" + + +class Solution(object): + def __init__(self, nums): + """ + :type nums: List[int] + """ + self.nums = nums + + def pick(self, target): + """ + :type target: int + :rtype: int + """ + cnt, res = 0, None + for i, n in enumerate(self.nums): + if n == target: + cnt += 1 + if (randint(0, cnt) % cnt) == 0: + res = i + return res + + +if __name__ == "__main__": + obj = Solution([1, 2, 3, 3, 3, 3]) + print(obj.pick(3)) + print(obj.pick(1)) + print(obj.pick(3)) |