aboutsummaryrefslogtreecommitdiff
path: root/random_pick_index.c
diff options
context:
space:
mode:
Diffstat (limited to 'random_pick_index.c')
-rw-r--r--random_pick_index.c50
1 files changed, 50 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
+}