[380] Insert Delete GetRandom O(1)

要死了寫了我兩天半 ！！！
雖然還包括了慌張的痛哭跟跑去象山沉澱心靈
但是C沒有內建的hash叫我寫這個真是太殘忍啦！！！
但是寫出來啦！！！
20ms 是網站上的最快啊啊啊啊啊啊！！！
雖然網站上根本只有不超過五個人submit過C吧我看！！！
原本最快的那個還偷吃步用別人寫好的hash  library
這樣還叫做implement嗎可以的話我也要用lib啊啊啊啊啊啊啊
要是面試出這個我就直接說你fire我吧我是庸才（結果人家根本沒聘妳XD)
反正就是非常想飆髒話的現在啊啊啊啊啊啊啊
為什麼都沒有人寫C !!! 為什麼！！！！！！

題目是說要有一個資料結構是insert , remove和getRandom 隨意取一個值用O(1)完成
這對C來講有多難你知道嗎你知道嗎（逼近出題的人）
數字不可重覆, 細節不多說了我被這題搞的好累(痛哭)

Insert Delete GetRandom O(1)
#define HASH_SIZE 997
typedef struct HashNodes{
    int value;
    int pos;
    struct HashNodes *next;
} HashNodes;

typedef struct {
    int size;
    int nums[10000];
    HashNodes **hashTable;
} RandomizedSet;

/** Initialize your data structure here. */
RandomizedSet* randomizedSetCreate() {
    RandomizedSet* myArray = malloc(sizeof (RandomizedSet));
    myArray->size = 0;
//    memset(myArray->nums , sizeof(int), 10000);
    myArray->hashTable = malloc(sizeof(HashNodes*)*HASH_SIZE);
    for (int i=0;i<HASH_SIZE; i++)
        myArray->hashTable[i] = NULL;
    return myArray;
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool randomizedSetInsert(RandomizedSet* obj, int val) {
    int index = abs(val % HASH_SIZE);
    HashNodes *ptr = obj->hashTable[index];
    HashNodes *pre = NULL;
    pre = ptr;

    while(ptr != NULL)
    {
        if (ptr->value == val)
            return false;

        pre = ptr;
        ptr = ptr->next;
    }
    obj->nums[obj->size] = val;
    ptr = malloc(sizeof(HashNodes));
    if (obj->hashTable[index]== NULL)
        obj->hashTable[index] = ptr;

    if (pre!=NULL)
        pre->next = ptr;

    ptr->pos = obj->size++;
    ptr->value = val;
    ptr->next = NULL;
    return true;
}

void updateIndex(RandomizedSet* obj, int target, int newIndex)
{
    int index = abs(target % HASH_SIZE);
    HashNodes *ptr = obj->hashTable[index];
    while(ptr != NULL)
    {
        if (ptr->value == target)
        {
            ptr->pos = newIndex;          
            break;
        }
        ptr = ptr->next;
    }
    return;  
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool randomizedSetRemove(RandomizedSet* obj, int val) {
    int index = abs(val % HASH_SIZE);
    HashNodes *ptr = obj->hashTable[index];
    HashNodes *pre = NULL;
    pre = ptr;

    while(ptr != NULL)
    {
        if (ptr->value == val)
        {
            updateIndex(obj, obj->nums[obj->size-1], ptr->pos);
            obj->nums[ptr->pos] = obj->nums[--obj->size];

            if (pre != ptr)
                pre->next = ptr->next;
            else//head
                obj->hashTable[index] = ptr->next;
            free(ptr);
            ptr = NULL;
            return true;
        }
        pre = ptr;
        ptr = ptr->next;
    }
    return false;
}

/** Get a random element from the set. */
int randomizedSetGetRandom(RandomizedSet* obj) {
    if (obj->size < 1)
        return NULL;
    int random = (rand()%obj->size);
    return obj->nums[random];
}

void randomizedSetFree(RandomizedSet* obj) {
#if 0
    for(int i=0;i<obj->size;i++)
        randomizedSetRemove(obj, obj->nums[i]);
    free(obj->hashTable);
    free(obj);
#endif

}

/**
 * Your RandomizedSet struct will be instantiated and called as such:
 * struct RandomizedSet* obj = randomizedSetCreate();
 * bool param_1 = randomizedSetInsert(obj, val);
 * bool param_2 = randomizedSetRemove(obj, val);
 * int param_3 = randomizedSetGetRandom(obj);
 * randomizedSetFree(obj);
 */