leetcode 380. 常數(shù)時間插入跷究、刪除和獲取隨機元素
題目要求我們實現(xiàn)一個數(shù)據(jù)結(jié)構(gòu)來支持插入、刪除和獲取隨機元素的時間復(fù)雜度都在O(1)之內(nèi)照藻。
難點和突破點：
我們都知道數(shù)組通過索引下標進行訪問是很快的饺鹃，但插入、刪除就不一樣了条霜，比如插入操作催什，需要在插入元素后，將插入位置后的所有元素都向后移動宰睡，以保證內(nèi)存的緊湊蒲凶、連續(xù)性，這需要O(n)的平均時間復(fù)雜度拆内。仔細想想旋圆，這個平均復(fù)雜度里面，最優(yōu)的復(fù)雜度是多少麸恍？
答案是O(1)灵巧，就是操作數(shù)組尾部元素時搀矫，可以達到O(1)的時間復(fù)雜度，對于插入尾部的操作刻肄，因為插入后本身就是數(shù)組的最后一個元素瓤球，所以不需要再移動后面的元素，而對于刪除操作亦是如此敏弃，刪除后不需要再將后面元素向前移動卦羡。
既然知道了操作尾部可以得到最優(yōu)的時間復(fù)雜度，那么我們要做的麦到，就是想辦法在每次的插入绿饵、刪除操作時，都只操作數(shù)組尾部瓶颠，以避免數(shù)據(jù)遷移拟赊；
抓住了這個特點，我們可以考慮用hash表來對val→index做一層映射：
1粹淋、對于插入操作要门，我們直接使用封裝好的ArrayList.add(T t)方法（只要不觸發(fā)擴容，那么該方法可以讓每次插入操作都插入到數(shù)組的尾部廓啊，為O(1)的時間復(fù)雜度）欢搜，同時我們把插入的元素以val→index（因為每次都是插入到最后，因此index就是數(shù)組尾部下標）的形式放入hash表中谴轮，后續(xù)刪除操作需要用到炒瘟；
2、對于刪除操作第步，我們要做的疮装，就是每次將數(shù)組尾部的元素lastVal與當(dāng)前要刪除的元素val的位置做一次調(diào)換（通過hash表找到val在數(shù)組中的索引下標），然后清空尾部粘都，釋放內(nèi)存即可廓推，做完這步后，還需要維護一下hash表翩隧，把目標元素占用的k-v對刪除掉樊展，同時更新lastVal在hash表中的索引映射。
3堆生、對于獲取隨機元素专缠，我們只需要在根據(jù)下標獲取元素時，對size做一個random后作為下標淑仆，即可隨機拿到一個元素涝婉。
代碼如下：
public class RandomizedSet {
// 存儲所有val
List<Integer> nums ;
// val->index哈希表，映射每個val在nums中的索引位置
Map<Integer, Integer> valToIndex;
Random random;
public RandomizedSet() {
nums = new ArrayList<>();
valToIndex = new HashMap<>();
random = new Random();
}
public boolean insert(int val) {
// 存在直接返回
if (valToIndex.containsKey(val)) {
return false;
}
// 直接添加到list中蔗怠，并用hash表記錄val在list中的下標
nums.add(val);
valToIndex.put(val, nums.size() - 1);
return true;
}
public boolean remove(int val) {
if (!valToIndex.containsKey(val)) {
return false;
}
// 1墩弯、找出val在nums中的索引
Integer valIdx = valToIndex.get(val);
// 2吩跋、取出nums尾部元素，替換val渔工，并刪除nums尾部（關(guān)鍵代碼）
Integer lastVal = nums.get(nums.size() - 1);
nums.set(valIdx, lastVal);
nums.remove(nums.size() - 1);
// 3锌钮、更新索引hash表，并remove掉val占用的entry
valToIndex.put(lastVal, valIdx);
valToIndex.remove(val);
return true;
}
public int getRandom() {
return nums.get(random.nextInt(nums.size()));
}
}
