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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
// 2121. Intervals Between Identical Elements
#include "leetcode.h"
/*
* given a 0-indexed array of 'n' integers 'arr'. the interval between two
* elements in 'arr' is defined as the absolute difference between their
* indices. more formally, the interval between 'arr[i]' and 'arr[j]' is |i -
* j|. return an array intervals of length 'n' where 'intervals[i]' is the sum
* of the intervals between 'arr[i]' and each element in 'arr' with the same
* value as 'arr[i]'.
*/
typedef struct {
int value;
uint64_t idx_sum;
int idx_max;
int idx_cnt;
int *idx;
} node;
typedef struct {
int size;
node *n;
} hash;
node *hash_find(hash *h, int v) {
int idx = v % h->size;
for (int i = 0; i < h->size; i++) {
int curr_idx = (idx + i) % h->size;
node *curr = &h->n[curr_idx];
if (!curr->idx_cnt || curr->value == v)
return curr;
}
return NULL;
}
long long *getDistances(int *arr, int arrSize, int *returnSize) {
long long *ans = calloc(arrSize, sizeof(long long));
hash h = {0, NULL};
h.size = arrSize * 2;
h.n = calloc(h.size, sizeof(node));
for (int i = 0; i < arrSize; i++) {
node *curr = hash_find(&h, arr[i]);
if (!curr->idx_cnt) {
curr->value = arr[i];
curr->idx_max = 10;
curr->idx = calloc(curr->idx_max, sizeof(int));
}
if (curr->idx_cnt == curr->idx_max) {
curr->idx_max *= 2;
curr->idx = realloc(curr->idx, curr->idx_max * sizeof(int));
}
curr->idx[curr->idx_cnt++] = i;
curr->idx_sum += i;
}
for (int i = 0; i < h.size; i++) {
node *curr = &h.n[i];
if (curr->idx_cnt) {
uint64_t pre_sum = 0, post_sum = curr->idx_sum;
for (int j = 0; j < curr->idx_cnt; j++) {
uint64_t curr_idx = curr->idx[j];
post_sum -= curr_idx;
ans[curr_idx] = (j * curr_idx - pre_sum) +
(post_sum - (curr->idx_cnt - j - 1) * curr_idx);
pre_sum += curr_idx;
}
free(curr->idx);
}
}
free(h.n);
*returnSize = arrSize;
return ans;
}
int main() {
int a1[] = {2, 1, 3, 1, 2, 3, 3}, a2[] = {10, 5, 10, 10};
int rs1 = 0, rs2 = 0;
long long *gd1 = getDistances(a1, ARRAY_SIZE(a1), &rs1);
long long *gd2 = getDistances(a2, ARRAY_SIZE(a2), &rs2);
for (int i = 0; i < ARRAY_SIZE(a1); i++)
printf("%lld ", gd1[i]); // expect: [4,2,7,2,4,4,5]
printf("\n");
for (int i = 0; i < ARRAY_SIZE(a2); i++)
printf("%lld ", gd2[i]); // expect: [5,0,3,4]
printf("\n");
free(gd1), free(gd2);
}
|