leetcode706-设计哈希映射

原题

不使用任何内建的哈希表库设计一个哈希映射

具体地说,你的设计应该包含以下的功能

  • put(key, value):向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在,更新这个值。
  • 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 (未找到)

注意:

  • 所有的值都在 [0, 1000000]的范围内。
  • 操作的总数目在[1, 10000]范围内。
  • 不要使用内建的哈希库。

解法

思想

偷懒,已知值的范围,直接将整数值映射为哈希值,有多少个哈希值建多少个桶,用空间换时间。(这里时间也换不了了,毕竟给1000000个元素赋初值还是挺耗时间的)

代码

class MyHashMap {
    int[] values;
    /** Initialize your data structure here. */
    public MyHashMap() {
        values = new int[1000001];
        Arrays.fill(values, -1);
    }

    /** value will always be non-negative. */
    public void put(int key, int value) {
        values[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 values[key];
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    public void remove(int key) {
        values[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);
 */

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode706-%e8%ae%be%e8%ae%a1%e5%93%88%e5%b8%8c%e6%98%a0%e5%b0%84/

(0)
彭晨涛彭晨涛管理者
上一篇 2019年12月17日
下一篇 2019年12月19日

相关推荐

  • leetcode25-K个一组翻转链表

    原题 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原…

    算法 2020年5月9日
    0540
  • leetcode1114-按序打印

    原题 我们提供了一个类: public class Foo {   public void one() { print("one"); }   public void two() …

    算法 2020年2月1日
    0140
  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110
  • leetcode394-字符串解码

    原题 给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意…

    算法 2019年12月13日
    090
  • leetcode141-环形链表

    原题 给定一个链表,判断链表中是否有环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没…

    2019年12月14日
    0100
  • leetcode124-二叉树中的最大路径和

    原题 给定一个非空二叉树,返回其最大路径和。 本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: 输入: [1…

    算法 2020年4月26日
    0170
  • 跳表-披着链表外衣的伪搜索树

    本文参考资源: 【数据结构与算法】之跳表(Java实现)---第九篇Java震哥聊校招-CSDN博客 跳表的原理及实例 - Rogn - 博客园 跳表Java实现Java偏离的定弦…

    2020年3月28日
    0670
  • leetcode23-合并K个排序链表

    原题 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [ 1->4->5, 1->3->4, 2->6 ] 输出: 1->1->2->3->…

    算法 2020年2月4日
    0170
  • leetcode118-杨辉三角

    原题 给定一个非负整数 numRows,生成杨辉三角的前 numRows 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 5 输出: [ [1], [1,1]…

    2019年11月15日
    0100
  • leetcode912-排序数组

    原题 给定一个整数数组 nums,将该数组升序排列。 示例 1: 输入: [5,2,3,1] 输出: [1,2,3,5] 示例 2: 输入: [5,1,1,2,0,0] 输出: […

    算法 2020年3月31日
    0350

发表回复

登录后才能评论