毎日のアルゴリズム(3)簡単な問題を探す

2種類の検索問題
一、有無を検索する(通常set;集合を使用する)
Ex:要素xは存在しますか?
二、対応関係の検索(キー値対応、map)
Ex:要素xは何回現れましたか.
次は2つの問題を通じて、この2つの問題をどのように解決するかを簡単に説明します.
1.leetcode 349から選択する.Intersection of Two Arrays
 

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
       set n1(nums1.begin(),nums1.end());
       set n2(nums2.begin(),nums2.end());
       vector res(n1.begin(),n1.end());
       for(set::iterator it = n2.begin(); it != n2.end(); it++) {
	   		if(n1.find(*it) != n1.end())
	   			res.push_back(*it);
	   }
	   
	   return res;
	}
};

注意:map、set、vectorなどのSTLコンテナを自分で使用する場合は、対応するヘッダファイルを必ず導入し、ネーミングスペースを宣言します.

#include
#include
using namespace std;

 2. leetcode 350を選択する.Intersection of Two Arrays

class Solution {
public:
    vector intersect(vector& nums1, vector& nums2) {
        map record;
        for( int i = 0 ; i < nums1.size() ; i++ ) {
            record[nums1[i]] ++;
        }
        vector res;
        for( int i = 0 ; i < nums2.size() ; i++ ) {
         if( record[nums2[i]] > 0 )  {
             res.push_back(nums2[i]);
             record[nums2[i]] --;
         }            
        }
        return res;
    }
};

最後に自分で整理したC++or CとSTL容器についての知識を共有します.
カーテンの中に整理してURLにアクセスします.
ドキュメントリンク:https://mubu.com/doc/11PSzN5UZsパスワード:qn 6 j