文章目录
- 1、哈希表结构
- 2、Java中的哈希表
- 3、leetcode217:统计重复元素
- 4、leetcode389:找不同
- 5、leetcode496:下一个更大元素
1、哈希表结构
又叫散列表,存键值对,将key用哈希函数转为数组下标索引
当两个不同的key经过哈希函数得到相同的结果i,即哈希冲突了
此时 i 位置就要存两个值,因此,链表出现,如下图中数组下标2的位置:
时间复杂度:根据key找value,时间复杂度为O(1),但如果有哈希冲突,则时间复杂度为O(k),k为冲突位置链表元素的个数
2、Java中的哈希表
下面这种用数组表示哈希表的结构,是key为下标索引,value为数组元素的值。重点关注HashMap就行:
3、leetcode217:统计重复元素
单论这题要return的结果,其实不借助数据结构,直接for循环遍历,里面再嵌套遍历一次,出现一个相等就直接return true就实现了。下面的解法,重点在有重复元素 + 每个重复元素分别重复了几次
哈希表的一个常见用途就是统计某个元素或字符出现的次数
统计思路:遍历数组,如果数组的元素e不在哈希表的key的集合中,则put(e, 1),反之,若在,则get这个key的value,并将其value更新为value+1。 再说这道题,要结果就遍历下HashMap,如果有value大于1的,则return true
public class P217 {public static boolean stats(int[] array) {if (null == array || array.length == 0) {return false;}Map<Integer, Integer> hashMap = new HashMap<>();for (int e : array) {if (!hashMap.containsKey(e)) {hashMap.put(e, 1);} else {int count = hashMap.get(e);hashMap.put(e, count + 1);}}// 统计完毕了,这里完成下题目的return值for (Integer value : hashMap.values()) {if (value > 1){return true;}}return false;}
}
测试:
public class P217 {public static void main(String[] args) {int[] array = {1, 2, 3, 4, 5, 1, 1};System.out.println(stats(array));}
}
效果:
4、leetcode389:找不同
用数组实现,还是哈希表的思路,将每个字母根据ASCII码转为数组下标,数组的值则存其出现的次数。两个注意点:
- a对应的ASCII码为97,没必要存97的位置,存0,b就存98 - a = 98 - 97 = 1
- 两个字符串,没必要对应两个数组,用一个,s字符串中的每个字母出现一次就减1,t字符串则加1,如此,最后数量不为1的位置,即为随机添加的那个字母
实现:
public class P389 {public static String findDifference(String t, String s) {if (s.length() == 0) {return t;}// 初始化一个空int数组,长度为26,因为最多26个字母int[] array = new int[26];char[] tArr = t.toCharArray();char[] sArr = s.toCharArray();for (char i : tArr) {// char类型转int即为其ASCII码array[(int)i - 97] = array[(int)i - 97] + 1;}for (char j : sArr) {array[(int)j - 97] = array[(int)j - 97] - 1;}for (int i = 0; i < array.length; i++) {if (array[i] > 0) {// 找到多余的字母以后,用其索引下标+97转回字符return (char)(i + 97) + "";}}return "";}
}
测试:
public class P389 {public static void main(String[] args) {String s = "abcd";String t = "abcda";System.out.println(findDifference(t, s));}
}
本质还是key-value的哈希表思想,不过是key的特殊性,用数组直接实现了。特别注意这里加一减一的思想,而不是用两个哈希表分别统计。
5、leetcode496:下一个更大元素
之前用两个栈解决过这题,还可用栈 + 哈希表解决,更加清晰。思路:直接计算num2中每个元素在num2中下一个更大的值,并存入哈希表,key为num2的每个元素,value为该元素的下一个更大的值。如此,遍历num1,直接从哈希表get,就可得到其下一个更大的值
计算num2中每个元素在num2中下一个更大的值,可借助栈,遍历num2,入栈,当即将入栈的元素a 大于 栈顶元素b的时候,即说明a是b的下一个更大的元素,存入map
public class P496Two {public static int[] findMore(int[] num1, int[] num2) {if (num1 == null || num2 == null || num1.length == 0 || num2.length == 0){return null;}//结果集int[] result = new int[num1.length];//栈和哈希表Stack<Integer> stack = new Stack<>();HashMap<Integer, Integer> map = new HashMap<>();// 栈不空,且即将入栈的元素大于栈顶元素的时候for (int num : num2) {while (stack.size() != 0 && num > stack.peek()) {// 即将入栈的元素就是栈顶元素的"下一个更大值",存入mapInteger key = stack.pop();map.put(key, num);}stack.push(num);}// 栈里还有元素的话,说明后面没有比它更大的了,统统弹栈,更大的值赋-1while (stack.size() != 0) {map.put(stack.pop(), -1);}// 到此,map中存了num2里每个元素的"下一个更大值",返回num1的for (int i = 0; i < num1.length; i++) {result[i] = map.get(num1[i]);}return result;}
}
测试下:
public class P496Two {public static void main(String[] args) {int[] num1 = {8, 1, 2};int[] num2 = {2, 1, 0, 8, 7, 6, 5};for (int i : findMore(num1, num2)) {System.out.print(i + " ");}}
}