练题100天——DAY27：两个数组交集Ⅱ+第三大的数
今天只有两道题呢，也很简单，难度★吧，能做出来。今天是有点懈怠了，但是还是撑着做了两道题，不是吗，不要太苛责自己，状态好的时候多写点，状态差的时候少写点，只要写了就不算原地踏步。
一.两个数组的交集Ⅱ ★☆☆☆☆
题目
350. 两个数组的交集 II 给你两个整数数组nums1和nums2，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
我的思路
这道题跟昨天的349. 两个数组的交集的区别是结果元素的次数不再局限为1次，而是要符合交集的次数，所以我用了相同的排序+双指针的方法，利用这个办法这道题看上去反而比昨天更简单了。
只需要先排序，然后在两个指针指向的元素相等时，赋值到结果数组res中，不相等时指向较小数的指针先后移动，直到其中一个指针移动到数组末尾即可。
代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { int len1=nums1.size(); int len2=nums2.size(); sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); vector<int> res; int p=0; int q=0; while(p<len1 && q<len2){ if(nums1[p]==nums2[q]){ res.push_back(nums1[p]); p++; q++; }else if(nums1[p]<nums2[q]){ p++; }else{ q++; } } return res; } };复杂度
时间复杂度：O(nlogn+mlogm+n+m)=O(nlogn+mlogm)
空间复杂度：O(logn+logm)
官方题解——哈希表
利用哈希表的value记录对应的key的“次数”，先循环数组1，保存每个数字的出现次数，然后遍历数组2的元素，如果该元素在哈希表中，则将其加入到结果数组中，同时将对应的value减一，表示已相等一次，若再次相等，一样的操作。然后，遍历完数组2即可。
代码
class Solution { public: vector<int> intersect(vector<int>& nums1, vector<int>& nums2) { int len1=nums1.size(); int len2=nums2.size(); vector<int> res; unordered_map<int,int> map; for(int i=0;i<len1;i++){ map[nums1[i]]++; } for(int i=0;i<len2;i++){ if(map.count(nums2[i])){ res.push_back(nums2[i]); map[nums2[i]]--; if(map[nums2[i]]==0){ map.erase(nums2[i]); } } } return res; } };复杂度
二.第三大的数 ★☆☆☆☆
题目
414. 第三大的数 给你一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。
思路
既然要找第三大的数字，那将数组排序后就更加容易寻找。
升序排列后，从数组最后一个元素开始向前寻找，用temp表示当前的新数值，即和前一个数字不一样的数，，用sign表示当前temp记录的是第几大的值，用res保存答案。遍历数组，遇到新数字就赋值给temp，并将sign加一，当sign==3时，temp记录的就是第三大的数值，赋值给res。
因为不满足第三大的情况都是输出最大值，所以给res初始化为最大值，没有满足的情况就直接输出最大值。
代码
class Solution { public: int thirdMax(vector<int>& nums) { //排序 //用标记值记录数值，慢慢向后移动找到第三大的数即可，反之输出最后一个数 int len=nums.size(); sort(nums.begin(),nums.end()); int temp=nums[len-1]; int sign=1; int res=nums[len-1]; for(int i=len-1;i>=0;i--){ if(nums[i]<temp){ temp=nums[i]; sign++; } if(sign==3){ res=temp; break; } } return res; } };复杂度
时间复杂度：O(n)。遍历数组最坏的情况为n次，所以时间复杂度为O(n)。
空间复杂度：O(1)。因为没有数组、哈希表这类的变量，只有普通变量，所以空间复杂度是常数。
官方题解
思路1——有序集合
创建有序集合set，利用其自动排序的特性存储前三大的元素，需要保证set长度一直<=3，如果加入了某元素，set>3，则要删去最小的元素。最后，若set==3：返回set中最小的值；反之，返回最大的值。
代码
class Solution { public: int thirdMax(vector<int>& nums) { set<int> s; for(int num:nums){ s.insert(num); if(s.size()>3){ s.erase(s.begin()); } } return s.size()==3?*s.begin():*s.rbegin(); } };说明
1.for (int num : nums)：表示依次取出容器（如vector、数组、set等）中的每个元素，赋值给变量num，并执行循环体，相当于
for (int i = 0; i < nums.size(); i++) { int num = nums[i]; // 手动通过下标取元素 }2.有序集合s：按升序排列，第一个元素s.begin()是最小的，最后一个元素s.rbegin()是最大的；s.erase(x)表示删除s中的元素x
复杂度
时间复杂度：O(n)。线性时间，s的操作因大小受限为常数级，遍历主导复杂度
空间复杂度：O(1)。常数空间，s最多存储 3 个元素，无额外空间开销
思路2——一次遍历
一次遍历顾名思义就是只需要将整个数组完整地遍历一次就实现功能，主要思想是借助变量a、b、c分别代表最大值、第二大值和第三大值，在遍历的过程中根据数组元素的大小改变三个变量的值。
nums[ i ]大于最大值：第二大变为第三大，原来的最大值变为第二大，当前元素变为最大值；第二大<nums[ i ]<最大值：第二大变为第三大，当前元素变为第二大；第三大<nums[ i ]<第二大：当前元素变为第三大。
最后返回时：若第三大c还是LONG_MIN表示没有前三大，返回最大值a；反之返回c
代码1
class Solution { public: int thirdMax(vector<int>& nums) { //用a、b、c模拟前三大元素 long a=LONG_MIN,b=LONG_MIN,c=LONG_MIN; for(long num:nums){ //大于最大数 if(num>a){ c=b; b=a; a=num; }//在第一大和第二大之间 else if(a>num && num>b){ c=b; b=num; } //在第二大和第三大之间 else if(b>num && num>c){ c=num; } } return c==LONG_MIN?a:c; } };代码2
第二种写法：利用指针a、b、c，初始化为空，表示无穷小，然后在判断范围时加上指针是否为空的判断
class Solution { public: int thirdMax(vector<int> &nums) { int *a = nullptr, *b = nullptr, *c = nullptr; for (int &num : nums) { if (a == nullptr || num > *a) { c = b; b = a; a = # } else if (*a > num && (b == nullptr || num > *b)) { c = b; b = # } else if (b != nullptr && *b > num && (c == nullptr || num > *c)) { c = # } } return c == nullptr ? *a : *c; } };复杂度
时间复杂度：O(n)
空间复杂度：O(1)