labuladong公众号算法学习笔记

查找、删除数组中任意元素

实现随机集合避开黑名单的随机数总结

实现随机集合

对于getRandom方法，如果想要[等概率]和[在O(1)的时间]取出元素就一定要满足：底层用数组实现，且数组必须是紧凑的。 对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度为O(1)，可以先把元素val交换到数组的尾部，然后pop出去。 交换两个元素需要索引来进行，则需要哈希表ValToIndex来记录每个元素值对应的索引。

class RandomizedSet{ public: //存储元素的值 vector<int> nums; //记录每个元素对应在nums中的索引 unordered_map<int,int> valToIndex; bool insert(int val){ //如果val已经存在，则不需要插入 if(valToIndex.count(val)) return false; //如果val不存在，则插入到数组尾部，并记录val对应的索引 valToIndex[val] = nums.size(); nums.push_back(val); return true; } bool remove(int val){ //若val不存在，不用删除 if(!valToIndex.count(val)) return false; //先拿到val的索引 int index = valToIndex[val]; //将最后一个元素对应的索引修改为index valToIndex[nums.back()] = index; //交换最后一个元素和val swap(nums[index],nums.back()); //在数组中删除元素val nums.pop_back(); //删除元素val对应的索引 valToIndex.erase(val); return true; } int getRandom(){ return nums[rand() % nums.size()]; } };

避开黑名单的随机数

可以将区间[0,N)看做一个数组，然后将blacklist中的元素移到数组最末尾，同时用一个哈希表进行映射。 对mapping[b]赋值时，要保证last一定不在blacklist中。

class Solution{ public: int sz; unordered_map<int,int> mapping; Solution(int N,vector<int>& blacklist){ sz=N-nums.size(); for(int b:black){ //赋值多少都可以，目的在于把键存在哈希表中， //方便快速判断数字是否在黑名单内 mapping[b]=666; } int last=N-1; for(int b:blacklist){ if(b>=sz){ continue; } while(mapping.count(last)){ last--; } mapping[b]=last; last--; } } int pick(){ int index=rand()%sz; //这个索引中了黑名单，需要被映射到其他位置 if(mapping.count(index)){ return mapping[index]; } //如果没有中黑名单，直接返回 return index; } };

总结

1、想要高效地，等概率地随机获取元素，就要使用数组作为底层容器。 2、要保持数组的紧凑性，可以把待删除元素换到最后，然后pop掉末尾的元素，这样复杂度为O(1)，需要额外的哈希表记录值到索引的映射。 3、数组中含有黑名单，可以利用哈希表巧妙处理映射关系，让数组在逻辑上紧凑，方便获取元素。