typedef struct {
int value;
int *idxs;
int size;
UT_hash_handle hh;
} Hash;
typedef struct {
Hash *hash_table;
int *nums;
int size;
} RandomizedCollection, RC;
/** Initialize your data structure here. */
RandomizedCollection* randomizedCollectionCreate() {
// printf("create\n");
RC *obj = malloc(sizeof(RC));
obj->hash_table = NULL;
obj->nums = malloc(0);
obj->size = 0;
return obj;
}
bool _insert(RC *obj, int value) {
// printf("insert : %d\n", value);
Hash *p;
HASH_FIND(hh, obj->hash_table,&value, sizeof(int), p);
bool flag;
if (p) {
flag = false;
p->idxs = realloc(p->idxs, (p->size + 1) * sizeof(int));
p->idxs[(p->size)++] = obj->size;
} else {
flag = true;
p = malloc(sizeof(Hash));
p->value = value;
p->size = 1;
p->idxs = malloc(sizeof(int));
p->idxs[0] = obj->size;
HASH_ADD(hh, obj->hash_table, value, sizeof(int), p);
}
obj->nums = realloc(obj->nums, (obj->size + 1) * sizeof(int));
obj->nums[(obj->size)++] = value;
return flag;
}
void printArr(RC *obj) {
for (int i=0; i<obj->size; ++i) {
printf("%d ", obj->nums[i]);
}
printf("\n");
}
bool randomizedCollectionInsert(RandomizedCollection* obj, int val) {
bool flag = _insert(obj, val);
//printArr(obj);
return flag;
}
bool _remove(RC *obj, int value) {
// printf("remove : %d\n", value);
Hash *p;
HASH_FIND(hh, obj->hash_table, &value, sizeof(int), p);
if (p && p->size > 0) {
int idx = p->idxs[--(p->size)];
if (idx != obj->size - 1) {
HASH_FIND(hh, obj->hash_table, &(obj->nums[obj->size-1]), sizeof(int), p);
p->idxs[p->size - 1] = idx;
for (int i=p->size-1; i-1>=0; --i) {
if (p->idxs[i] > p->idxs[i-1]) break;
int t = p->idxs[i];
p->idxs[i] = p->idxs[i-1];
p->idxs[i-1] = t;
}
obj->nums[idx] = p->value;
}
obj->size -= 1;
return true;
} else {
return false;
}
}
bool randomizedCollectionRemove(RandomizedCollection* obj, int val) {
bool flag = _remove(obj, val);
// printArr(obj);
return flag;
}
/** Get a random element from the collection. */
int _random(RC *obj) {
// printf("Random\n");
if (obj->size == 0) return -1;
return obj->nums[rand() % obj->size];
}
int randomizedCollectionGetRandom(RandomizedCollection* obj) {
return _random(obj);
}
void randomizedCollectionFree(RandomizedCollection* obj) {
Hash *cur, *tmp;
HASH_ITER(hh, obj->hash_table, cur, tmp) {
HASH_DEL(obj->hash_table, cur);
free(cur->idxs);
free(cur);
}
free(obj->nums);
free(obj);
}
typedef struct {
int value;
int *idxs;
int size;
UT_hash_handle hh;
} Hash;
typedef struct {
Hash *hash_table;
int *nums;
int size;
} RandomizedCollection, RC;
/** Initialize your data structure here. */
RandomizedCollection* randomizedCollectionCreate() {
// printf("create\n");
RC *obj = malloc(sizeof(RC));
obj->hash_table = NULL;
obj->nums = malloc(0);
obj->size = 0;
return obj;
}
bool _insert(RC *obj, int value) {
// printf("insert : %d\n", value);
Hash *p;
HASH_FIND(hh, obj->hash_table,&value, sizeof(int), p);
bool flag;
if (p) {
flag = false;
p->idxs = realloc(p->idxs, (p->size + 1) * sizeof(int));
p->idxs[(p->size)++] = obj->size;
} else {
flag = true;
p = malloc(sizeof(Hash));
p->value = value;
p->size = 1;
p->idxs = malloc(sizeof(int));
p->idxs[0] = obj->size;
HASH_ADD(hh, obj->hash_table, value, sizeof(int), p);
}
obj->nums = realloc(obj->nums, (obj->size + 1) * sizeof(int));
obj->nums[(obj->size)++] = value;
return flag;
}
void printArr(RC *obj) {
for (int i=0; i<obj->size; ++i) {
printf("%d ", obj->nums[i]);
}
printf("\n");
}
bool randomizedCollectionInsert(RandomizedCollection* obj, int val) {
bool flag = _insert(obj, val);
//printArr(obj);
return flag;
}
bool _remove(RC *obj, int value) {
// printf("remove : %d\n", value);
Hash *p;
HASH_FIND(hh, obj->hash_table, &value, sizeof(int), p);
if (p && p->size > 0) {
int idx = p->idxs[--(p->size)];
if (idx != obj->size - 1) {
HASH_FIND(hh, obj->hash_table, &(obj->nums[obj->size-1]), sizeof(int), p);
p->idxs[p->size - 1] = idx;
for (int i=p->size-1; i-1>=0; --i) {
if (p->idxs[i] > p->idxs[i-1]) break;
int t = p->idxs[i];
p->idxs[i] = p->idxs[i-1];
p->idxs[i-1] = t;
}
obj->nums[idx] = p->value;
}
obj->size -= 1;
return true;
} else {
return false;
}
}
bool randomizedCollectionRemove(RandomizedCollection* obj, int val) {
bool flag = _remove(obj, val);
// printArr(obj);
return flag;
}
/** Get a random element from the collection. */
int _random(RC *obj) {
// printf("Random\n");
if (obj->size == 0) return -1;
return obj->nums[rand() % obj->size];
}
int randomizedCollectionGetRandom(RandomizedCollection* obj) {
return _random(obj);
}
void randomizedCollectionFree(RandomizedCollection* obj) {
Hash *cur, *tmp;
HASH_ITER(hh, obj->hash_table, cur, tmp) {
HASH_DEL(obj->hash_table, cur);
free(cur->idxs);
free(cur);
}
free(obj->nums);
free(obj);
}