LeetCode 솔루션

706. Design HashMap

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.04.21 20:52

3,763 조회
4 댓글
0 추천
0 비추천
목록 게시글 쓰기

[LeetCode 시즌 3] 2022년 4월 21일 문제입니다

[Easy] 706. Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

0 <= key, value <= 106
At most 104 calls will be made to put, get, and remove.

#leetcode, #문제풀이, #시즌3, #easy, #Amazon, #Microsoft, #Linkedin, #Salesforce, #Oracle, #Apple, #ServiceNow, #Goldman Sachs, #Walmart Global Tech, #Bloomberg, #array, #hash table, #linked list, #design, #hash function

링크

https://leetcode.com/problems/design-hashmap/ 1422 회 연결

익명
작성일 2022.04.22 23:53

Runtime: 367 ms, faster than 12.11% of C++ online submissions for Design HashMap.
Memory Usage: 50.4 MB, less than 97.45% of C++ online submissions for Design HashMap.

class MyHashMap {
private:
    struct node{
        int key;
        int value;
    };
    node tmp;
public:
    std::vector<node> m;
    MyHashMap() {
        
    }
    
    void put(int key, int value) {
        int n=m.size();
        bool flag=true;
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                m[i].value = value;
                flag = false;
            };
        };
        if(flag){
            tmp.key=key;
            tmp.value=value;
            m.push_back(tmp);
        };
        return ;
    }
    
    int get(int key) {
        int n=m.size();
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                return m[i].value;
            };
        };
        return -1;
    }
    
    void remove(int key) {
        int n=m.size();
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                m.erase(m.begin()+i);
                return ;
            };
        };
    }
};

Runtime: 367 ms, faster than 12.11% of C++ online submissions for Design HashMap.
Memory Usage: 50.4 MB, less than 97.45% of C++ online submissions for Design HashMap.

[code=C++]class MyHashMap {
private:
    struct node{
        int key;
        int value;
    };
    node tmp;
public:
    std::vector<node> m;
    MyHashMap() {
        
    }
    
    void put(int key, int value) {
        int n=m.size();
        bool flag=true;
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                m[i].value = value;
                flag = false;
            };
        };
        if(flag){
            tmp.key=key;
            tmp.value=value;
            m.push_back(tmp);
        };
        return ;
    }
    
    int get(int key) {
        int n=m.size();
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                return m[i].value;
            };
        };
        return -1;
    }
    
    void remove(int key) {
        int n=m.size();
        for(int i=0;i<n;i++){
            if(m[i].key == key){
                m.erase(m.begin()+i);
                return ;
            };
        };
    }
};[/code]

익명
작성일 2022.04.23 01:28

Runtime: 400 ms, faster than 74.00% of Swift online submissions for Design HashMap.
Memory Usage: 49.8 MB, less than 5.00% of Swift online submissions for Design HashMap.

class MyHashMap {

    var arr: [Int?] = []
    
    init() {
    }
    
    // O(n)
    func put(_ key: Int, _ value: Int) {
        if key >= arr.count {   
            arr += [Int?](repeating: nil, count: key + 1 - arr.count)
        }
        arr[key] = value
    }
    
    // O(n)
    func get(_ key: Int) -> Int {
        guard key < arr.count, let value = arr[key] else { return -1 }
        return value
    }
    
    // O(n)
    func remove(_ key: Int) {
        guard key < arr.count, arr[key] != nil else { return }
        arr[key] = nil
    }
}

/**
 * Your MyHashMap object will be instantiated and called as such:
 * let obj = MyHashMap()
 * obj.put(key, value)
 * let ret_2: Int = obj.get(key)
 * obj.remove(key)
 */

익명
작성일 2022.04.24 18:28

Runtime: 22 ms, faster than 74.74% of Java online submissions for Design HashMap.
Memory Usage: 61.5 MB, less than 60.51% of Java online submissions for Design HashMap.

class MyHashMap {

    
    HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
    
    public MyHashMap() {
        this.hashMap = new HashMap<Integer, Integer>();
    }
    
    public void put(int key, int value) {
        hashMap.put(key, value);
    }
    
    public int get(int key) {
        return hashMap.getOrDefault(key, -1);
        
    }
    
    public void remove(int key) {
        hashMap.remove(key);
    }
}

익명
작성일 2022.04.27 15:50

Runtime: 5432 ms
Memory Usage: 17.1 MB

class MyHashMap:

    def __init__(self):
        self.hashMap = []        

    def put(self, key: int, value: int) -> None:
        if not self.hashMap:
            self.hashMap.append([key, value])
        else:
            for i in range(len(self.hashMap)):
                if self.hashMap[i][0] == key:
                    self.hashMap[i][1] = value
                    return
            else:
                self.hashMap.append([key, value])
                    

    def get(self, key: int) -> int:
        if not self.hashMap:
            return -1
        for i in range(len(self.hashMap)):
            if self.hashMap[i][0] == key:
                return self.hashMap[i][1]
        return -1

    def remove(self, key: int) -> None:
        if not self.hashMap:
            return
        for i in range(len(self.hashMap)):
            if self.hashMap[i][0] == key:
                del self.hashMap[i]
                return