[数据结构与算法]JAVA-数据结构-哈希表-附leetcode

JAVA-数据结构-哈希表-附leetcode

1.简介

哈希表也叫散列表

键值对 key -> value

eg: 2019141022318 -> 张三

时间复杂度

（碰撞 O(k) ）

2.JAVA 哈希表基本操作

public static void main(String[] args) {
        // 创建哈希表
        String[] hashTable = new String[4];

        HashMap<Integer,String> map = new HashMap<>();

        // 添加元素 O(1)
        hashTable[1] = "hanmeimei";
        hashTable[2] = "lihua";
        hashTable[3] = "siyangyuan";

        map.put(1,"hanmeimei");
        map.put(2,"lihua");
        map.put(3,"siyangyuan");

        //更新元素 O(1)
        hashTable[1] = "xiaoming";
        map.put(1,"xioaming");

        //删除元素 O(1)
        hashTable[1] = "";
        map.remove(1);

        //获取元素 O(1)
        String temp = hashTable[3];
        map.get(3);
        
        //检查key是否存在 数组方式创建的不太好找 O(1)
        map.containsKey(3);
        
        //长度 O(1)
        map.isEmpty();

    }

3.Leetcode练习题

217.存在重复元素

统计结构 一一对应 1-n次 2-n次 3-n次 4-n次 所以用哈希表

数组长度不确定，用JAVA自带的hashmap

key 存取数组元素 value存取数组元素出现次数

简介方法用HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。

public boolean containsDuplicate(int[] nums) {
        //定义HashSet 
        Set<Integer> set = new HashSet<Integer>();
        //遍历数组 HashSet不允许存在相同值，所以如果无法加入，就证明寄了
        for(int x : nums){
            if(!set.add(x)){
                return true;
            }
        }
        return false;

    }

389 找不同

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            cnt[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); ++i) {
            char ch = t.charAt(i);
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
}

public char findTheDifference(String s, String t) {
        //来自可爱的饲养员姐姐
        int sizeS = s.length();
        int sizeT = t.length();
        //如果s为空，那么直接返回t第一个元素
        if(sizeS == 0){
            return t.charAt(0);
        }
        int[] table = new int[26];
        //遍历两个数组，前一个数组有的 都- 后一个数组有的都+
        for(int i = 0; i<sizeT; i++){
            if(i<sizeS){
                //求出ASCII码
                table[s.charAt(i) - 'a']++;
            }
            table[t.charAt(i) - 'a']--;
        }

        for(int i = 0; i < 26; i++){
            //遍历数组，找到那个不为零的值
            if(table[i] != 0){
                //+a回到原来的ASCII码，然后转化成对应字母
                return (char)('a' + i);
            }
        }
        return 'a';


    }