题目来源:https://leetcode.com/problems/intersection-of-two-arrays/
题目难度:Easy
解答1[Java]
1 | import java.util.Arrays; |
复杂度分析
没错,hashSet的contains方法是调用map.containsKey(O)方法的,containsKey(o)是根据hash函数去做散列的,所以与元素的多少无关,无论是多少元素containsKey(o)的时间复杂度基本上O(1)。
解答2[Java]:
1 | import java.util.Arrays; |
思路
很巧妙的一个算法,先把一个数组的最大值和最小值圈起来。
复杂度分析
空间复杂度:
result 数组和 exist 数组为 $O(m)$ 或者 $O(h)$。m 和 h 是两个数组的长度。
时间复杂度:$O(n)$。