【OJ】前K个高频单词和两个数组的交集

zxctscl

发布于 2024-11-30 12:43:34

7000

代码可运行

文章被收录于专栏：zxctscl个人专栏zxctscl个人专栏

运行总次数：0

代码可运行

个人主页 ： zxctscl 如有转载请先通知 以下两道题目均来自力扣

1. 692. 前K个高频单词

1.1 分析

先试用map来统计每个单词出现的次数：

        map<string,int> dict;
       for(auto& e:words)
       {
        dict[e]++;
       }

这时候单词是按照字典序排列的，但是频率是乱的。

可以直接用sort来排一下频率，在取出前k个就行。但要用pair来排序，pair是支持比较大小的:

这里期望的是用second去比较，而不是用first，这时候，就得用一个仿函数：两个pair比较，按照scond去比较，排的是降序

struct kvCom
{
  bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
  {
    return kv1.second > kv2.second;
  }
};

sort是一个函数模板，这里是类模板，传的是仿函数对象： sort(v.begin(),v.end(),kvCom());

排序完了，就得取出前k个的单词放在一个新vector里面：

vector<string> vRet;
       for(size_t i=0;i<k;++i)
       {
            vRet.push_back(v[i].first);
       }
      return vRet;

此时的代码：

class Solution {
public:
struct kvCom
{
  bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
  {
    return kv1.second > kv2.second;
  }
};
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> dict;
       for(auto& e:words)
       {
        dict[e]++;
       }

       vector<pair<string,int>> v(dict.begin(),dict.end());
       sort(v.begin(),v.end(),kvCom());
       
       vector<string> vRet;
       for(size_t i=0;i<k;++i)
       {
            vRet.push_back(v[i].first);
       }
      return vRet;
    }
};

但是这里只过了部分的测试用例：

这里有一部分没有按照字典序排，这里是因为sort底层是快排排序不稳定，要修改可以把sort换成稳定的stable_sort: stable_sort(v.begin(),v.end(),kvCom()); 这时候就可以了：

还可以修改仿函数：当second相同的时候，按照字典序从小到大排

struct kvCom
{
  bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
  {
    return kv1.second > kv2.second||(kv1.second==kv2.second && kv1.first < kv2.first);
  }
};

1.2 代码

用稳定排序：

class Solution {
public:
struct kvCom
{
  bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
  {
    return kv1.second > kv2.second;
  }
};
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> dict;
       for(auto& e:words)
       {
        dict[e]++;
       }

       vector<pair<string,int>> v(dict.begin(),dict.end());
       stable_sort(v.begin(),v.end(),kvCom());
       
       vector<string> vRet;
       for(size_t i=0;i<k;++i)
       {
            vRet.push_back(v[i].first);
       }
      return vRet;
    }
};

修改仿函数：

class Solution {
public:
struct kvCom
{
  bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2)
  {
    return kv1.second > kv2.second||(kv1.second==kv2.second && kv1.first < kv2.first);
  }
};
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> dict;
       for(auto& e:words)
       {
        dict[e]++;
       }

       vector<pair<string,int>> v(dict.begin(),dict.end());
       sort(v.begin(),v.end(),kvCom());
       
       vector<string> vRet;
       for(size_t i=0;i<k;++i)
       {
            vRet.push_back(v[i].first);
       }
      return vRet;
    }
};

2. 349. 两个数组的交集

2.1 分析

两个数组中都有重复的值，可以先用set去重，排序： set<int> s1(nums1.begin(),nums1.end()); set<int> s2(nums2.begin(),nums2.end());

两个数组都排好序了，比较两个数组，从小到大：

定义两个变量，遍历两个数组，如果两个变量对应值都相同，相同的值就是两个数组的交集，记录下之后，同时都往后走。如果两个值不相同，小的那个值对应的往后走，直到一个数组遍历完。

2.2 代码

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(),nums1.end());
        set<int> s2(nums2.begin(),nums2.end());

     vector<int> ret;
    auto it1=s1.begin();
    auto it2=s2.begin();
	while (it1 != s1.end() && it2 != s2.end())
	{
        if(*it1<*it2)
        {
            it1++;
        }
         else if(*it1>*it2)
         {
                 it2++;
         }
		else
        {
            ret.push_back(*it1);
            it1++;
            it2++;    
        }     
        
	}
    return ret;
	    
    }
};