2017年12月14日 星期四

[LeetCode] 350. Intersection of Two Arrays II

轉自LeetCode

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.
<Solution>

這題是 349. Intersection of Two Arrays 的衍生題

差別在於,這次重覆了幾次,答案裡面就要有幾次

思考方向不變,只是改用 hash map,因為要記錄幾次

code如下

C++
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
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
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()
}
}

沒有留言:

張貼留言