Given two arrays, write a function to compute their intersection.
Example:
Given nums1 =[1, 2, 2, 1] , nums2 = [2, 2] , return [2, 2] .
Given nums1 =
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
這題是 349. Intersection of Two Arrays 的衍生題
差別在於,這次重覆了幾次,答案裡面就要有幾次
思考方向不變,只是改用 hash map,因為要記錄幾次
code如下
C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { | |
vector<int> ans; | |
unordered_map<int, int> hashmap; | |
for(const int &n : nums1) { | |
hashmap[n]++; | |
} | |
for(const int &n : nums2) { | |
if(hashmap.find(n) != hashmap.end() && hashmap[n]-- > 0) { | |
ans.push_back(n); | |
} | |
} | |
return ans; | |
} | |
}; |
Java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public int[] intersect(int[] nums1, int[] nums2) { | |
HashMap<Integer, Integer> map = new HashMap<>(); | |
for(final int n : nums1) { | |
map.put(n, map.getOrDefault(n, 0) + 1); | |
} | |
ArrayList<Integer> tmpAns = new ArrayList<>(); | |
for(final int n : nums2) { | |
if(map.containsKey(n) && map.put(n, map.get(n)-1) > 0) { | |
tmpAns.add(n); | |
} | |
} | |
int[] ans = new int[tmpAns.size()]; | |
int i = 0; | |
for(final int n : tmpAns) { | |
ans[i++] = n; | |
} | |
return ans; | |
} | |
} |
Kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
fun intersect(nums1: IntArray, nums2: IntArray): IntArray { | |
val map = mutableMapOf<Int,Int>() | |
for(n in nums1) { | |
map[n] = map[n]?.let{it+1} ?: 1 | |
} | |
val ans = arrayListOf<Int>() | |
for(n in nums2) { | |
if(map[n] != null && map[n]!! > 0) { | |
ans.add(n) | |
map[n] = map[n]!! - 1 | |
} | |
} | |
return ans.toIntArray() | |
} | |
} |
沒有留言:
張貼留言