查找问题

• 查找有无（只有键）

  • 元素'a'是否存在
  • set（集合）

• 查找对应关系（键值对应）

  • 元素'a'出现了几次
  • map（字典）

• set和map的底层实现是红黑树

• 常见操作

  • insert()
  • find()
  • erase()
  • change(map)：改变某个键对应的值

要求

• 给定两个数组nums，求两个数组的公共元素
• 输出结果中每个元素唯一
• 不考虑输出结果的顺序

举例

• nums1=[1,2,2,1]
• nums2=[2,2]
• 结果：[2]

实现

• 将公共元素放入公共的set中

  1 class Solution{
  2 public:
  3 vector intersection(vector& nums1, vector& nums2){
  4
  5 set record;
  6 for(int i = 0 ; i < nums1.size() ; i ++ ) 7 record.insert( nums1[i] ); 8 9 set resultSet;
  10 for( int i = 0 ; i < nums2.size() ; i ++ ) 11 if( record.find(nums2[i]) != record.end()) 12 resultSet.insert(nums2[i]); 13 14 vector resultVector;
  15 for( set::iterator iter = resultSet.begin() ; iter != resultSet.end() ; iter ++)
  16 resultVector.push_back( *iter );
  17
  18 return resultVector;
  19 }
  20 };

• 简单写法

  1 class Solution{
  2 public:
  3 vector intersection(vector& nums1, vector& nums2){
  4
  5 set record( nums1.begin(), nums1.end());
  6
  7 set resultSet;
  8 for( int i = 0 ; i < nums2.size() ; i ++ ) 9 if( record.find(nums2[i]) != record.end()) 10 resultSet.insert(nums2[i]); 11 12 return vector resultVector(resultSet.begin(),resultSet.end());
  13
  14 }
  15 };

  参考

• set查找时间复杂度

  • https://www.cnblogs.com/jiezai/p/11149932.html