leetcode解题: Intersection of two arrays (349)

发表于 | 分类于

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.

解法1：Sort + Two pointers O(NlogN) Time + O(1) Space

先考虑将两个数组排序，然后只需要维护两个指针，对于一样的数值就放入返回数组中。同时要考虑去重的情况。这点上九章的答案做的比我更简洁。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        std::sort(nums1.begin(), nums1.end());
        std::sort(nums2.begin(), nums2.end());
        int ptr1 = 0;
        int ptr2 = 0;
        vector<int> res;
        while (ptr1 < nums1.size() && ptr2 < nums2.size()) {
            while (ptr1 > 0 && ptr1 < nums1.size() && nums1[ptr1] == nums1[ptr1-1]) ++ptr1;
            while (ptr2 > 0 && ptr2 < nums2.size() && nums2[ptr2] == nums2[ptr2 - 1]) ++ptr2;
            if (ptr1 == nums1.size()) break;
            if (ptr2 == nums2.size()) break;
            if (nums1[ptr1] < nums2[ptr2]) {
                ++ptr1;
            } else if (nums1[ptr1] > nums2[ptr2]) {
                ++ptr2;
            } else {
                res.emplace_back(nums1[ptr1]);
                ++ptr1;
                ++ptr2;
            }
        }
        return res;
    }
};

Java

1

解法2： HashTable O(N) Time + O(N) Space

先扫描第一个数组，建立hashtable，然后扫描第二个数组，同时维持一个结果的hashtable用来去重。
C++
用到了unordered_map’s iterate method.

1
2
3
unordered_map<int, bool> map; // define a map
map.begin() 和 map.end() return iterator of the map, can be used like
for (auto a = map.begin(); a!= map.end(); a++) {}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, bool> map;
        unordered_map<int, bool> res;
        for (int num: nums1) {
            map[num] = true;
        }
        for (int num: nums2) {
            if (map[num] && !res[num])
                res[num] = true;
        }
        // iterate over map
        vector<int> res_vector;
        for (auto iterator = res.begin(); iterator != res.end(); iterator++) {
            if (iterator->second) {
                res_vector.emplace_back(iterator->first);
            }
        }  
        return res_vector;
    }
};

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums1) {
            set.add(num);
        }
        Set<Integer> res = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                res.add(num);
            }
        }
        int[] result = new int[res.size()];
        int i = 0;
        for (int num : res) {
            result[i++] = num;
        }
        return result;
    }
}