diff options
author | Jack Sangdahl <[email protected]> | 2024-08-20 17:38:34 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-08-20 17:38:34 -0600 |
commit | 53ef9811af1c9e013ba8e9f379ea67724ffc0281 (patch) | |
tree | 784ea191a74eb03a43346897c0efb2f5f0ad0b41 /range_freq_queries.c | |
parent | b756e65c613e0f145c671d089e30b62ae6f63959 (diff) | |
download | leetcode-53ef9811af1c9e013ba8e9f379ea67724ffc0281.tar.gz leetcode-53ef9811af1c9e013ba8e9f379ea67724ffc0281.zip |
2080. range frequency queries
Diffstat (limited to 'range_freq_queries.c')
-rw-r--r-- | range_freq_queries.c | 75 |
1 files changed, 75 insertions, 0 deletions
diff --git a/range_freq_queries.c b/range_freq_queries.c new file mode 100644 index 0000000..41f289d --- /dev/null +++ b/range_freq_queries.c @@ -0,0 +1,75 @@ +// 2080. Range Frequency Queries +#include "leetcode.h" + +/* + * design a data structure to find the frequency of a given value in a given + * subarray. the frequency of a value in a subarray is the number of occurences + * of that value in the subarray. implement the 'RangeFreqQuery' class: + * 'rangeFreqQueryCreate(int[] arr)' constructs an instance of the class with + * the given 0-indexed integer array 'arr'. 'int RangeFreqQuery(int left, int + * right, int val)' returns the frequency of 'val' in the subarray 'arr[left ... + * right]'. a subarray is contiguous sequence of elements within an array. + * 'arr[left ... right]' denotes the subarray that contains the elements of + * 'nums' between indices 'left' and 'right' inclusively + */ + +typedef struct { + int *a; + int size; +} RangeFreqQuery; + +int cmp(const void *a, const void *b) { return (*(int *)a - *(int *)b); } + +RangeFreqQuery *rangeFreqQueryCreate(int *arr, int arrSize) { + RangeFreqQuery *obj = (RangeFreqQuery *)calloc(1, sizeof(RangeFreqQuery)); + obj->size = arrSize + 1; + obj->a = (int *)calloc(obj->size, sizeof(int)); + for (int i = 0; i < arrSize; i++) + obj->a[i] = arr[i] << 17 | i; + obj->a[arrSize] = 10001 << 17; + qsort(obj->a, obj->size - 1, sizeof(int), cmp); + return obj; +} + +int bsearch1(int *a, int size, int target) { + int l = 0, r = size - 1, m; + while (l < r) { + m = l + ((r - l) >> 1); + if (a[m] < target) + l = m + 1; + else + r = m; + } + return l; +} + +int bsearch2(int *a, int size, int target) { + int l = 0, r = size - 1, m; + while (l < r) { + m = l + ((r - l) >> 1); + if (a[m] <= target) + l = m + 1; + else + r = m; + } + return l; +} + +int rangeFreqQueryQuery(RangeFreqQuery *obj, int left, int right, int value) { + int l = bsearch1(obj->a, obj->size, value << 17 | left); + int r = bsearch2(obj->a, obj->size, value << 17 | right); + return r - l; +} + +void rangeFreqQueryFree(RangeFreqQuery *obj) { + free(obj->a); + free(obj); +} + +int main() { + int arr[] = {12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56}; + RangeFreqQuery *obj = rangeFreqQueryCreate(arr, ARRAY_SIZE(arr)); + printf("%d\n", rangeFreqQueryQuery(obj, 1, 2, 4)); // expect: 1 + printf("%d\n", rangeFreqQueryQuery(obj, 0, 11, 33)); // expect: 2 + rangeFreqQueryFree(obj); +} |