Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

349. Intersection of two arrays

Topic describes

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2]Copy the code

Example 2:

Input: nums1 =,9,5 [4], nums2 =,4,9,8,4 [9] output: [9, 4]Copy the code

Violence law

Use the set lookup algorithm to determine whether elements in NUMs1 exist in NUMs2.

【c++ common search algorithm 】

class Solution
{
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        // Returns an array of results
        vector<int> ret;

        for (int i = 0; i < nums1.size(a); i++) {// Find elements in nums1 in nums2
            vector<int>::iterator it = find(nums2.begin(), nums2.end(), nums1[i]);
            // If found
            if(it ! = nums2.end())
            {
                // Check whether the result array already exists
                vector<int>::iterator it2 = find(ret.begin(), ret.end(), nums1[i]);
                // Does not exist, add the number to the result array
                if (it2 == ret.end())
                {
                    ret.push_back(nums1[i]); }}}returnret; }};Copy the code

Hash method

  • 1. It is stated in the statement that the order of elements is not considered, and the weight is removed.
  • 2, problems limit the size of the number can use arrays to solve hash class problems
  • 3. Considering the above two problems, we can use the set
  • 4. The set is divided intoset multi_set unordered_set
  • 5unordered_set
class Solution
{
public:
    / / the hash method
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2)
    {
        // Returns an array of results
        vector<int> ret;
        Nums1 and nums2 are de-processed
        unordered_set<int> nums1_set(nums1.begin(), nums1.end());
        unordered_set<int> nums2_set(nums2.begin(), nums2.end());
        Nums2_set = nums2_set = nums2_set
        for (int num : nums1_set)
        {
            unordered_set<int>::iterator it = nums2_set.find(num);
            if(it ! = nums2_set.end())
            {
                ret.push_back(num); }}returnret; }};Copy the code