380. Insert Delete GetRandom O(1)

Input
["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"]
[[],[1],[2],[2],[],[1],[2],[]]

Output
[null, true, false, true, 2, true, false, 2]

// 演算法 / Algorithm:
//   nums: 動態陣列存放實際的值 / dynamic array of the actual values
//   pos : 雜湊表 val -> 在 nums 的 index / hash map from val to its index in nums
//   刪除時把目標跟最後一個元素交換再 pop_back / on remove, swap-with-last then pop_back
// 我們用 LeetCode 預先提供的 uthash.h 來實作雜湊表 / we use uthash.h (provided by LeetCode's C judge).

#include <stdlib.h>      // malloc, realloc, free, rand / 記憶體配置與隨機數
#include <stdbool.h>     // bool, true, false / 布林型別
#include "uthash.h"      // uthash 雜湊表巨集 / uthash macros for the hash map

typedef struct {
    int key;             // 鍵就是 val 本身 / the key is the value itself
    int idx;             // 該 val 在 nums 中的 index / its index inside nums[]
    UT_hash_handle hh;   // uthash 內部用的 handle，必須叫 hh / required handle field, must be named hh
} Entry;

typedef struct {
    int *nums;           // 指向動態陣列的指標 / pointer to the dynamic array
    int size;            // 目前元素個數 / current number of elements
    int cap;             // 已配置的容量 / currently allocated capacity
    Entry *map;          // uthash 的「表頭」指標，初始必須是 NULL / hash table head pointer, must start as NULL
} RandomizedSet;

RandomizedSet* randomizedSetCreate(void) {
    RandomizedSet *obj = (RandomizedSet*)malloc(sizeof(RandomizedSet));  // 配置物件 / allocate the struct
    obj->cap  = 16;                                                      // 初始容量設 16 / start with capacity 16
    obj->size = 0;                                                       // 一開始沒元素 / no elements yet
    obj->nums = (int*)malloc(sizeof(int) * obj->cap);                    // 配置初始陣列 / allocate the underlying array
    obj->map  = NULL;                                                    // uthash 規定表頭一開始要設 NULL / uthash requires NULL to start
    return obj;
}

bool randomizedSetInsert(RandomizedSet* obj, int val) {
    Entry *e = NULL;                                                     // 暫存查詢結果的指標 / pointer to receive lookup result
    HASH_FIND_INT(obj->map, &val, e);                                    // 在雜湊表中找 key=val / look up val in the hash map
    if (e != NULL) return false;                                         // 已存在就不能再插入 / already present, reject

    if (obj->size == obj->cap) {                                         // 陣列滿了要擴容 / grow the array if full
        obj->cap *= 2;                                                   // 容量加倍（攤銷 O(1)） / double the capacity (amortized O(1))
        obj->nums = (int*)realloc(obj->nums, sizeof(int) * obj->cap);    // 重新配置更大的記憶體 / reallocate to the new size
    }
    obj->nums[obj->size] = val;                                          // 把 val 放到陣列尾端 / append val at the end of nums

    e = (Entry*)malloc(sizeof(Entry));                                   // 為雜湊表新節點配置記憶體 / allocate a new hash entry
    e->key = val;                                                        // 設定鍵 / set the key
    e->idx = obj->size;                                                  // 記住它在 nums 的 index / remember its index in nums
    HASH_ADD_INT(obj->map, key, e);                                      // 加入雜湊表 / insert it into the hash table

    obj->size++;                                                         // 元素數 +1 / size grows by one
    return true;                                                         // 成功插入 / inserted successfully
}

bool randomizedSetRemove(RandomizedSet* obj, int val) {
    Entry *e = NULL;                                                     // 接收查詢結果 / lookup target
    HASH_FIND_INT(obj->map, &val, e);                                    // 找 val 是否存在 / look up val
    if (e == NULL) return false;                                         // 不存在就不能刪 / not in set, nothing to remove

    int idx      = e->idx;                                               // 要被刪除的位置 / index slot to vacate
    int lastIdx  = obj->size - 1;                                        // 陣列最後一個位置 / index of the last element
    int lastVal  = obj->nums[lastIdx];                                   // 拿到最後一個值 / grab the last value

    obj->nums[idx] = lastVal;                                            // 把最後一個值搬到要刪的位置 / move last value into the hole

    if (idx != lastIdx) {                                                // 若不是同一位置才需更新對應 / only update map if it actually moved
        Entry *eLast = NULL;                                             // 拿 lastVal 的雜湊節點 / fetch lastVal's hash entry
        HASH_FIND_INT(obj->map, &lastVal, eLast);                        // 從雜湊表找 lastVal / look up the moved value
        eLast->idx = idx;                                                // 更新它的新 index / update its index to the freed slot
    }

    HASH_DEL(obj->map, e);                                               // 從雜湊表移除舊節點 / remove the old entry
    free(e);                                                             // 釋放它的記憶體 / free its memory
    obj->size--;                                                         // 元素數 -1（相當於 pop_back） / shrink size (logical pop_back)
    return true;                                                         // 成功刪除 / removed successfully
}

int randomizedSetGetRandom(RandomizedSet* obj) {
    int r = rand() % obj->size;                                          // 取 [0, size) 的均勻隨機 index / uniform random index in [0, size)
    return obj->nums[r];                                                 // 直接以 index 取值即 O(1) / O(1) lookup by index
}

void randomizedSetFree(RandomizedSet* obj) {
    Entry *cur, *tmp;                                                    // 走訪雜湊表用的兩個指標 / iterators for safe deletion
    HASH_ITER(hh, obj->map, cur, tmp) {                                  // 遍歷整張雜湊表 / iterate through every entry
        HASH_DEL(obj->map, cur);                                         // 從表中移除節點 / unlink it
        free(cur);                                                       // 釋放節點記憶體 / free its memory
    }
    free(obj->nums);                                                     // 釋放動態陣列 / free the underlying array
    free(obj);                                                           // 釋放物件本身 / free the struct itself
}

// 演算法 / Algorithm:
//   nums: vector<int> 存實際值 / vector storing the actual values
//   pos : unordered_map<int,int> val -> nums 的 index / map from value to its index
//   刪除採用 swap-with-last + pop_back / removal swaps target with last then pop_back

#include <vector>          // std::vector / 動態陣列容器
#include <unordered_map>   // std::unordered_map / 雜湊表容器
#include <cstdlib>         // std::rand / C 風格隨機數

class RandomizedSet {
private:
    std::vector<int> nums;                          // 動態陣列存元素 / array of current elements
    std::unordered_map<int, int> pos;               // val -> nums 的 index / map: value to its index in nums

public:
    RandomizedSet() {}                              // 預設建構即可（容器自帶初始化） / default ctor; containers self-initialize

    bool insert(int val) {
        if (pos.count(val)) return false;           // 已存在就拒絕 / reject if already present
        pos[val] = nums.size();                     // 新元素的 index 是目前 size / its index will be the current size
        nums.push_back(val);                        // 追加到陣列尾端 / append at the end
        return true;                                // 成功插入 / inserted
    }

    bool remove(int val) {
        auto it = pos.find(val);                    // 用 find 拿到 iterator 避免兩次查找 / single lookup via find
        if (it == pos.end()) return false;          // 找不到就不能刪 / not present, nothing to do

        int idx = it->second;                       // 取得要刪位置 / index of the slot to vacate
        int lastVal = nums.back();                  // 取得最後一個值 / grab last value of nums

        nums[idx] = lastVal;                        // 把最後一個值搬到要刪位置 / move last value into the hole
        pos[lastVal] = idx;                         // 更新被搬動值的新 index / update map for the moved value
        nums.pop_back();                            // 陣列尾端去掉一個 / shrink the array by one
        pos.erase(it);                              // 從雜湊表抹掉 val / erase val from the map
        return true;                                // 成功刪除 / removed
    }

    int getRandom() {
        return nums[std::rand() % nums.size()];     // 隨機 index 後直接取值 / O(1) random index then index lookup
    }
};