Given two arrays, write a function to compute their intersection.
Example:
Given nums1 =[1, 2, 2, 1]
, nums2 = [2, 2]
, return [2, 2]
. Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
题目标签:Hash Table
题目给了我们两个array, 让我们找到相交的数字,这一题与 #349 一样,只是可以包括重复的数字。
所以利用HashMap 把 nums1 的数字和 出现次数存入;
比较nums2 和 map1 把相交的数字 和 次数 存入 intersect;
最后把intersect 里的 数字 按照它的出现次数 存入 int[] res。
Java Solution:
Runtime beats 23.67%
完成日期:06/05/2017
关键词:HashMap
关键点:利用两个HashMap
1 class Solution 2 { 3 public int[] intersect(int[] nums1, int[] nums2) 4 { 5 HashMapmap1 = new HashMap<>(); 6 HashMap intersect = new HashMap<>(); 7 int[] res; 8 int len = 0; 9 int pos = 0;10 11 // store nums1 numbers into map112 for(int n: nums1)13 map1.put(n, map1.getOrDefault(n, 0) + 1);14 15 16 // compare nums2 with map1, store intersected numbers into intersect17 for(int n: nums2)18 {19 if(map1.containsKey(n))20 {21 intersect.put(n, intersect.getOrDefault(n, 0) + 1);22 len++;23 24 map1.put(n, map1.get(n) - 1);25 26 if(map1.get(n) == 0)27 map1.remove(n);28 }29 30 }31 32 res = new int[len];33 34 for(int n: intersect.keySet())35 {36 for(int i=0; i
参考资料:N/A
LeetCode 题目列表 -