Intersection of Two Arrays

Description

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

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

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

Challenge
Can you implement it in three different algorithms?

Link

Lintcode_ladder

Method

1. use hash table to record duplications
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param nums1 an integer array
     * @param nums2 an integer array
     * @return an integer array
     */
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        // Write your code here
        if (nums1.empty() || nums2.empty()) {
            return {};
        }
        vector<int> result;
        int n1 = nums1.size();
        int n2 = nums2.size();
        // value number
        unordered_map<int, bool> dict;
        for (int i = 0; i < n1; ++i) {
            dict[nums1[i]] = false;
        }
        // find match
        for (int i = 0; i < n2; ++i) {
            if (dict.find(nums2[i]) != dict.end()) {
                if (dict.find(nums2[i])->second == false) {
                     result.push_back(nums2[i]);
                     dict[nums2[i]] = true;
                }
            }
        }
        return result;
    }
};

Similar problems

x

Tags

x