常數時間插入、删除、擷取元素 哈希表day06

leetcode380 常數時間插入、删除和擷取随機元素

這道題想到了使用哈希表，但是單使用哈希表并不能直接做到傳回随機值O(1)。想了一個小時都沒想到怎麼做，然後本弱雞厚顔無恥的取看了題解，思路參考本題的官方題解

複習哈希表

介紹

• 定義：散清單（Hash table，也叫哈希表），是根據關鍵碼值(Key)而直接進行通路的資料結構。散清單可以使用數組 + 連結清單的方式來實作。
• 哈希函數：哈希表查找過程是根據Key來算出hashcode（通常是一個數字），根據這個數字來随機通路數組，而理論上兩個不同的key是可以算出同樣的hashcode的。這個就叫做哈希沖突。

  

• 哈希表的性能：構造一個沖突小，穩定性高的hash函數是很重要的，我們在刷題的時候大部分時間都不會去考慮這個問題，但是實際工程中有時不可避免需要我們自己構造hash函數，這時就要根據實際情況進行分析測試啦。

常用操作的時間複雜度

• 插入：O(1)
• 删除：O(1)
• 查找：O(1)

需要使用的java知識

Random類

Random() r = new Random()
           

生成任意整數(-231到231-1之間)

int n1 = r.nextInt();//直接使用nextInt方法即可。
           

生成[0,10)區間的整數

int n2 = r.nextInt(10);//使用這種方式可以生成任意區間的随機數
  int n3 = r. nextInt(10)+3//生成的就是[3,13)這個區間的随機數
           

解題思路

剽竊原答案的圖檔，畫的真好看

哈希表+動态數組

Insert:

• 添加元素到動态數組。
• 在哈希表中添加值到索引的映射

  

remove:

• 在哈希表中查找要删除元素的索引。
• 将要删除元素與最後一個元素交換。
• 删除最後一個元素。
• 更新哈希表中的對應關系。

  

class RandomizedSet {
    private ArrayList<Integer> value =new ArrayList<>();//存放值
    private Map<Integer,Integer> map=new HashMap<>();//存關系


    /** Initialize your data structure here. */
    public RandomizedSet() {

    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        else {
            map.put(val,value.size());
            value.add(val);
            return true;
        }
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        else {
            int last_ele=value.get(value.size()-1);//拿到清單的最後一個元素
            int index=map.get(val);//通過值(key)拿到目前要删除元素的下标
            value.set(index,last_ele);//這裡不能用add(index,ele),因為使用這個是添加元素，清單會變長
            map.put(last_ele,index);//相應的把map的值也更新了
            value.remove(value.size()-1);//把最後一個元素删掉，因為此使原來的最後一個元素已經和與要删除的元素交換了
            map.remove(val);//清除map中的這個元素
            return true;
        }
    }

    /** Get a random element from the set. */
    public int getRandom() {
        if (value==null) throw new RuntimeException("清單為空");
        Random rd=new Random();
        int i = rd.nextInt(value.size());
        return value.get(i);
    }
}