1. 题目描述

problem link

Design a data structure that supports all following operations in average O(1) time. Note: Duplicate elements are allowed.

  1. insert(val): Inserts an item val to the collection.
  2. remove(val): Removes an item val from the collection if present.
  3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

2. 解题

又AC了一道Hard，趁脑袋还热乎着赶紧写一篇blog记录一下。

首先，增删都是O(1)的数据结构，我能想到的也只有哈希表了，所以这题要求的数据结构首先要基于哈希表。然后用拉链法解决冲突。

然后最重要的限制条件是，从这个数据结构中取一个随机数的时间复杂度也是O(1)，并且要求数据结构中每个数据被选到的几率是和这个数在数据结构中出现了几次是线性相关的。首先我解决选择几率和出现次数线性相关这个问题的大方向是，除了哈希表的链表外，再拿一个数组记录所有存在哈希表里的数据，并且用一个size变量记录数组中有几个元素。每次insert一个元素，除了把它插入哈希表外，我还要把它插入数组的末尾。这样每次我取随机数，只需要在[ 0, size )这个范围内取一个随机数，然后把数组中下标是随机数的那个元素返回就行了。但这个方法看似解决了选择随机数的时间复杂度，但其实可以发现删除元素不仅得在哈希表里删除，也得在数组中删除，但如果数组中的数据都随意的存在末尾的话，我在数组中查找指定元素又不能O(1)了，因为数组元素和哈希表元素没有一个对应的关系可以让我直接找到该元素。那怎么解决呢？

可以这样，在哈希表元素中加一个条目arrayIndex，记录这个元素在insert进来的时候，存进数组时它的下标。这样，我删除某一个元素的时候，用O(1)就可以找到对应的哈希表元素，然后在这个元素中又得到它在数组中的下标，然后又可以用O(1)在数组中把它也删除了，这样，就彻底解决插入删除取随机数都是O(1)的问题。

之后就是一些细节方面的问题了。我必须保证数组中的N个元素都是存储在数组的前N项中的，这样才能正常的取[ 0, size )的随机数。那如果我删除了一个数组中间的元素，就必须把数组最末尾的元素移到这个被删除的位置上，然后记得把哈希表中对应条目的arrayIndex也改了。

3. 代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define HTCAPACITY 5000

typedef int bool;
#define true 1
#define false 0

typedef struct _htItem {
    struct _htItem* next;
    int arrayIndex;
    int val;
}htItem;

typedef struct {
    htItem** ht;
    int array[HTCAPACITY];
    int size;  // 记录array中有多少个数
} RandomizedCollection;

/** Initialize your data structure here. */
RandomizedCollection* randomizedCollectionCreate() {
    RandomizedCollection* rc =
        (RandomizedCollection*)malloc(sizeof(RandomizedCollection));
    rc->ht = (htItem **)malloc(sizeof(htItem *) * HTCAPACITY);
    for (int i = 0; i < HTCAPACITY; i++) {
        rc->ht[i] = (htItem *)malloc(sizeof(htItem));
        rc->ht[i]->next = NULL;
        rc->ht[i]->arrayIndex = -1;
        rc->ht[i]->val = -1;
    }
    memset(rc->array, 0, sizeof(int) * HTCAPACITY);
    rc->size = 0;

    return rc;
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
bool randomizedCollectionInsert(RandomizedCollection* obj, int val) {
    // hash
    int index = (val % HTCAPACITY);
    index = index >= 0 ? index : index + HTCAPACITY;

    // insert
    bool sign = true;
    htItem* ptr = obj->ht[index];
    while (ptr->next != NULL) {
        ptr = ptr->next;
        if (ptr->val == val) {
            sign = false;
        }
    }
    ptr->next = (htItem *)malloc(sizeof(htItem));
    ptr->next->val = val;
    ptr->next->next = NULL;

    // 把这个数加入array
    obj->array[obj->size] = val;
    ptr->next->arrayIndex = obj->size;
    obj->size++;

    return sign;
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
bool randomizedCollectionRemove(RandomizedCollection* obj, int val) {
    // hash
    int index = (val % HTCAPACITY);
    index = index >= 0 ? index : index + HTCAPACITY;

    // find
    bool sign = false;
    htItem* ptr = obj->ht[index];
    while (ptr->next != NULL && ptr->next->val != val) {  // 在这条链表中寻找val
        ptr = ptr->next;
    }
    if (ptr->next == NULL) {  // 如果没找到
        return sign;
    }
    else {  // ptr->next就是要删除的元素
        htItem* item = ptr->next;

        // 从哈希表中删除这个元素
        ptr->next = ptr->next->next;  
        
        // 从array中删除这个元素
        if (obj->size == 1) {  // 如果数组中只有这一个元素
            obj->size--;
        }
        else {
            if (item->arrayIndex == obj->size - 1) {  // 如果这个元素在数组最末尾
                obj->size--;
            }
            else {  // 如果这个元素不在最末尾，则让最末尾元素覆盖这个位置，同时要修改哈希表中这个元素的arrayIndex
                obj->array[item->arrayIndex] = obj->array[obj->size - 1];
                int data = obj->array[obj->size - 1];  // data是末尾元素的数值

                // 在哈希表中找data
                int tmpIndex = (data % HTCAPACITY);
                tmpIndex = tmpIndex >= 0 ? tmpIndex : tmpIndex + HTCAPACITY;
                htItem* tmpPtr = obj->ht[tmpIndex];
                tmpPtr = tmpPtr->next;
                while (tmpPtr->arrayIndex != obj->size - 1) {
                    tmpPtr = tmpPtr->next;
                }
                tmpPtr->arrayIndex = item->arrayIndex;  // 把新的数组下标赋值        

                obj->size--;
                free(item);
            }
        }
        return true;
    }
}

/** Get a random element from the collection. */
int randomizedCollectionGetRandom(RandomizedCollection* obj) {
    int index = rand() % (obj->size);
    return obj->array[index];
}

void randomizedCollectionFree(RandomizedCollection* obj) {
    for (int i = 0; i < HTCAPACITY; i++) {
        free(obj->ht[i]);
    }
    free(obj);
}

/**
 * Your RandomizedCollection struct will be instantiated and called as such:
 * struct RandomizedCollection* obj = randomizedCollectionCreate();
 * bool param_1 = randomizedCollectionInsert(obj, val);
 * bool param_2 = randomizedCollectionRemove(obj, val);
 * int param_3 = randomizedCollectionGetRandom(obj);
 * randomizedCollectionFree(obj);
 */

int main() {
    srand((unsigned int)time(0));
    RandomizedCollection* obj = randomizedCollectionCreate();
    bool sign;
    sign = randomizedCollectionInsert(obj, 3);
    sign = randomizedCollectionInsert(obj, 4);
    sign = randomizedCollectionInsert(obj, 3);
    sign = randomizedCollectionRemove(obj, 3);
    sign = randomizedCollectionRemove(obj, 3);
    printf("\n");

    system("pause");
    return 0;
}
最后修改：2021 年 11 月 28 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏