【原】?LeetCode刷題實(shí)戰(zhàn)380：O(1) 時(shí)間插入、刪除和獲取隨機(jī)元素

程序IT圈 2021-09-13

展開全文

算法的重要性，我就不多說(shuō)了吧，想去大廠，就必須要經(jīng)過(guò)基礎(chǔ)知識(shí)和業(yè)務(wù)邏輯面試+算法面試。所以，為了提高大家的算法能力，這個(gè)公眾號(hào)后續(xù)每天帶大家做一道算法題，題目就從LeetCode上面選！

今天和大家聊的問(wèn)題叫做 O(1) 時(shí)間插入、刪除和獲取隨機(jī)元素，我們先來(lái)看題面：

https:///problems/insert-delete-getrandom-o1/

設(shè)計(jì)一個(gè)支持在平均時(shí)間復(fù)雜度 O(1) 下，執(zhí)行以下操作的數(shù)據(jù)結(jié)構(gòu)。

insert(val)：當(dāng)元素 val 不存在時(shí)，向集合中插入該項(xiàng)。

remove(val)：元素 val 存在時(shí)，從集合中移除該項(xiàng)。

getRandom：隨機(jī)返回現(xiàn)有集合中的一項(xiàng)。每個(gè)元素應(yīng)該有相同的概率被返回。

示例

// 初始化一個(gè)空的集合。
RandomizedSet randomSet = new RandomizedSet();

// 向集合中插入 1 。返回 true 表示 1 被成功地插入。
randomSet.insert(1);

// 返回 false ，表示集合中不存在 2 。
randomSet.remove(2);

// 向集合中插入 2 。返回 true 。集合現(xiàn)在包含 [1,2] 。
randomSet.insert(2);

// getRandom 應(yīng)隨機(jī)返回 1 或 2 。
randomSet.getRandom();

// 從集合中移除 1 ，返回 true 。集合現(xiàn)在包含 [2] 。
randomSet.remove(1);

// 2 已在集合中，所以返回 false 。
randomSet.insert(2);

// 由于 2 是集合中唯一的數(shù)字，getRandom 總是返回 2 。
randomSet.getRandom();

解題

利用動(dòng)態(tài)數(shù)組的下標(biāo)索引實(shí)現(xiàn)常數(shù)時(shí)間內(nèi)的插入和隨機(jī)元素的訪問(wèn)，

再利用哈希表實(shí)現(xiàn)常數(shù)時(shí)間的刪除操作：將刪除元素和最后一個(gè)元素交換，將最后一個(gè)元素刪除

class RandomizedSet {
private:
unordered_map<int,int> hash;//哈希實(shí)現(xiàn)刪除
vector<int> v;//動(dòng)態(tài)數(shù)組實(shí)現(xiàn)插入和隨機(jī)訪問(wèn)
public:
/** Initialize your data structure here. */
RandomizedSet() {

}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
//當(dāng)元素 val 不存在時(shí)，向集合中插入該項(xiàng)。
bool insert(int val) {
  if(hash.find(val) != hash.end()) return false; //如果集合中已經(jīng)存在val，返回false，
  v.push_back(val);//否則插入到數(shù)組末尾
  hash[val] = v.size() - 1;//
  return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
//元素 val 存在時(shí)，從集合中移除該項(xiàng)。
bool remove(int val) {
  if(hash.find(val) == hash.end()) return false;//如果集合中不存在val，返回false
  int lastPos = v.size() - 1;//數(shù)組最后一個(gè)元素位置
  int valPos = hash[val];//將被刪除值和數(shù)組最后一位進(jìn)行交換
  v[valPos] = v[lastPos];
  v.pop_back();//刪除
  hash[v[valPos]] = valPos;//被交換的值下標(biāo)發(fā)生變化，需要更新
  hash.erase(val); //哈希表中刪除val的項(xiàng)
  return true;
}

/** Get a random element from the set. */
//隨機(jī)返回現(xiàn)有集合中的一項(xiàng)。每個(gè)元素應(yīng)該有相同的概率被返回。
int getRandom() {
int size = v.size();
int pos = rand() % size;//對(duì)下標(biāo)產(chǎn)生隨機(jī)數(shù)
return v[pos];//數(shù)組可以根據(jù)下表返回
}
};

/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet* obj = new RandomizedSet();
* bool param_1 = obj->insert(val);
* bool param_2 = obj->remove(val);
* int param_3 = obj->getRandom();
*/