力扣网编程380题：时间的插入、删除和获取随机元素（动态数组+线性搜索）

一. 简介

前面的一篇文章使用哈希表+动态数组思路解决了力扣网的题目：时间的插入，删除和获取随机元素。哈希表的操作调用了 C第三方库uthash来实现的，文章如下：

力扣网编程380题：时间的插入、删除和获取随机元素（哈希表+动态数组思路）-CSDN博客

本文使用了 动态数组 + 线性搜索的思路。

二. 力扣网编程380题：时间的插入、删除和获取随机元素（哈希表思路）

题目要求：你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

解题思路二：（C实现简易版的哈希表）

本文使用了 动态数组 + 线性搜索的思路。不过可能有两个函数的时间复杂度不能满足题目要求。

1. 创建数组接口，注意创建好内存后，还需要初始化内存和一些变量值。例如数组元素个数，数组缓存大小；

2. 插入元素：判断新元素是否已存在数组中，不存在则可以插入；

3. 删除元素：判断元素是否已存在数组中，存在则删除：删除方法是将数组最后一个元素移到待删除的元素位置，数组元素个数cnt--，这样保证数组元素0~cnt-1连续完整。

4. 生成随机数接口，不用多说；

5. 释放缓存接口：注意释放缓存时判断指针是否为NULL和缓存释放的顺序；

判断指针是否NULL，为了避免堆空间被重复释放；

缓存释放顺序应该首先释放结构体中数组内存，再释放结构体指针的内存。

C语言实现如下：

#define  NO_EXIST  -1

typedef struct {
  int* nums;   //数组
  int cnt;     //数组中元素个数
  int capacity; //数组容量 
} RandomizedSet;


RandomizedSet* randomizedSetCreate() {
    RandomizedSet* obj = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    if(!obj) {
        return NULL;
    }

    obj->nums = (int*)malloc(16*sizeof(int));
    if(!obj->nums){
        free(obj);
        return NULL;
    }
    obj->cnt = 0;
    obj->capacity = 16;
    //初始化时间种子
    srand(time(NULL));
    return obj;
}
//向数组中插入元素
bool randomizedSetInsert(RandomizedSet* obj, int val) {
    if(!obj){
        return false;
    }    
    //检查元素是否已存在数组中
    int index = -1;
    for(int i = 0; i < obj->cnt; i++){
        if(obj->nums[i] == val) {
            index = i;
            break;
        }
    }
    if(index != -1) { //元素已存在数组中
        return false;
    }
    //数组元素个数超过数组容量时，进行数组扩容
    if((obj->cnt) >= obj->capacity) {
        int* new_nums = (int*)realloc(obj->nums, 2*obj->capacity*sizeof(int));
        obj->nums = new_nums;
        obj->capacity = 2*obj->capacity;
    }

    //插入元素
    obj->nums[obj->cnt] = val;
    obj->cnt++; 
    return true;
}

//删除某个元素
bool randomizedSetRemove(RandomizedSet* obj, int val) {
    if(!obj){
        return false;
    }    
    int index = NO_EXIST;
    //在数组中查找元素
    for(int i = 0; i< obj->cnt; i++) {
        if(obj->nums[i] == val) {
            index = i;
            break;
        }
    }
    if(index == -1) { //说明元素不存在数组中
        return false;
    }

    //将数组最后一个元素放到待删除元素的位置
    obj->nums[index] = obj->nums[obj->cnt -1];
    obj->cnt--;
    return true;
}
//从数组中获取随机元素
int randomizedSetGetRandom(RandomizedSet* obj) {
    if(!obj || (obj->cnt == 0)) {
        return -1;
    }

    //使用随机数生成随机数
    unsigned int seed = rand();
    int random_i = ((unsigned long long)seed * RAND_MAX + rand()) % obj->cnt;
    return obj->nums[random_i];
}
//释放缓存
void randomizedSetFree(RandomizedSet* obj) {
    if(obj){
        if(obj->nums) {
            free(obj->nums);
            obj->nums = NULL;
        }
        free(obj);
        obj = NULL;
    }
}

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

可以看出，这种使用动态数组的解法，插入元素接口时间复杂度为O(n)，删除元素接口的时间复杂度为O(n)， 超过了题目要求的的O(1)。