[LeetCode] 349. Intersection of Two Arrays

轉自LeetCode

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

<Solution>

這題白話來說，就是要找出兩個 array中，相同的值有哪些

想法如下

• 歷遍一個 array，並用一個 hash set 來記錄

• 再歷遍另一個 array，並使用另一個 hash set 記錄相同的值。為什麼還要用一個 hash set 來記錄，是因為最後的答案，重複的值要剔除

code 如下

C++

	class Solution {
	public:
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
	unordered_set<int> tmpAns;
	unordered_set<int> hashset;
	for(const int &n : nums1) {
	hashset.insert(n);
	}
	for(const int &n : nums2) {
	if(hashset.count(n)) {
	tmpAns.insert(n);
	}
	}
	return vector<int>(tmpAns.begin(), tmpAns.end());
	}
	};

view raw intersectionOfTwoArray.cpp hosted with ❤ by GitHub

Java

	class Solution {
	public int[] intersection(int[] nums1, int[] nums2) {
	HashSet<Integer> tmpAns = new HashSet<>();
	HashSet<Integer> set = new HashSet<>();
	for(final int n : nums1) {
	set.add(n);
	}
	for(final int n : nums2) {
	if(set.contains(n)) {
	tmpAns.add(n);
	}
	}
	int[] ans = new int[tmpAns.size()];
	int i = 0;
	for(final int n : tmpAns) {
	ans[i++] = n;
	}
	return ans;
	}
	}

view raw intersectionOfTwoArray.java hosted with ❤ by GitHub

或是只用一個 set 也是可以

	class Solution {
	fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
	val set = nums1.toMutableSet()
	val ans = arrayListOf<Int>()
	for(n in nums2) {
	if(set.contains(n)) {
	ans.add(n)
	set.remove(n)
	}
	}
	return ans.toIntArray()
	}
	}

view raw intersection_of_two_arrays.kt hosted with ❤ by GitHub