LeetCode演算法題-Design HashMap(Java實現)
這是悅樂書的第299 次更新,第318 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第167題(順位題號是706)。在不使用任何內建雜湊表庫的情況下設計HashMap。具體而言,你的設計應包括以下功能:
put(key,value):將一個(key,value)對插入HashMap。如果該值已存在於HashMap中,請更新該值。
get(key):返回指定鍵對映到的值,如果此對映不包含鍵的對映,則返回-1。
remove(key):如果此對映包含鍵的對映,則刪除值鍵的對映。
例如:
MyHashMap hashMap = new MyHashMap();
hashMap.put(1,1);
hashMap.put(2,2);
hashMap.get(1); //返回1
hashMap.get(3); //返回-1(未找到)
hashMap.put(2,1); //更新現有值
hashMap.get(2); //返回1
hashMap.remove(2); //刪除2的對映
hashMap.get(2); //返回-1(未找到)
注意:
-
所有key和value都將在[0,1000000]範圍內。
-
操作次數將在[1,10000]範圍內。
-
請不要使用內建的HashMap庫。
本次解題使用的開發工具是eclipse,jdk使用的版本是1.8,環境是win7 64位系統,使用Java語言編寫和測試。
02 第一種解法
為了實現鍵值對的效果,內層使用了二維陣列,外層使用ArrayList。其中二維陣列是一個一行兩列的結構,第一行第一列儲存key的值,第一行第二列儲存value的值。另外,我們還需要單獨寫一個contains方法,來判斷當前的key是否存在於HashMap中。
put方法的時間複雜度為O(n),get方法的時間複雜度為O(n),remove的時間複雜度為O(n),contains方法的時間複雜度為O(n)。
class MyHashMap { List<int[][]> list; /** Initialize your data structure here. */ public MyHashMap() { list = new ArrayList<int[][]>(); } /** value will always be non-negative. */ public void put(int key, int value) { if (contains(key)) { for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { arr[0][1] = value; break; } } } else { list.add(new int[][]{{key, value}}); } } public boolean contains(int key){ for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { return true; } } return false; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { for (int[][] arr : list) { if (arr != null && arr[0][0] == key) { return arr[0][1]; } } return -1; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { if (contains(key)) { for (int i=0; i<list.size(); i++) { if (list.get(i)[0][0] == key) { list.remove(i); break; } } } } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */
03 第二種解法
我們也可以使用一個小track,依舊使用陣列,但是變成了一維陣列,因為題目給定了key和value的範圍,所以陣列的容量為其最大範圍加1。因為最小值可以為0,而陣列預設值是0,避免誤判,將陣列的初始值全部賦值為-1。
put方法的時間複雜度為O(1),get方法的時間複雜度為O(1),remove的時間複雜度為O(1),但是空間複雜度較高。
class MyHashMap { int[] arr; /** Initialize your data structure here. */ public MyHashMap() { arr = new int[1000001]; Arrays.fill(arr, -1); } /** value will always be non-negative. */ public void put(int key, int value) { arr[key] = value; } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { return arr[key]; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { arr[key] = -1; } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */
04 第三種解法
使用單鏈表,此解法是參考至討論區。傳送門:https://leetcode.com/problems/design-hashmap/discuss/227081/Java-Solutions
class MyHashMap { /** Initialize your data structure here. */ ListNode[] nodes; public MyHashMap() { nodes = new ListNode[10000]; } /** value will always be non-negative. */ public void put(int key, int value) { int idx = key%10000; if(nodes[idx]==null){ nodes[idx] = new ListNode(-1,-1); nodes[idx].next = new ListNode(key,value); }else{ ListNode pre = find(nodes[idx], key); if(pre.next == null){ pre.next = new ListNode(key, value); }else{ pre.next.value = value; } } } /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */ public int get(int key) { int idx = key%10000; if(nodes[idx] == null) return -1; else{ ListNode pre = find(nodes[idx], key); if(pre.next == null) return -1; else return pre.next.value; } } public ListNode find(ListNode root, int key){ ListNode pre = null; ListNode cur = root; while(cur!=null && cur.key != key){ pre = cur; cur = cur.next; } return pre; } /** Removes the mapping of the specified value key if this map contains a mapping for the key */ public void remove(int key) { int idx = key%10000; if(nodes[idx] == null) return; else{ ListNode pre = find(nodes[idx], key); if(pre.next == null) return; else{ pre.next = pre.next.next; } } } class ListNode{ int key; int value; ListNode next; ListNode(int key, int value){ this.key = key; this.value = value; } } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */
05 小結
演算法專題目前已日更超過四個月 ,演算法題文章167 +篇,公眾號對話方塊回覆【資料結構與演算法 】、【演算法 】、【資料結構 】中的任一關鍵詞,獲取系列文章合集。
以上就是全部內容,如果大家有什麼好的解法思路、建議或者其他問題,可以下方留言交流,點贊、留言、轉發就是對我最大的回報和支援!