郑州网站建设开拓者青岛的互联网企业

郑州网站建设开拓者,青岛的互联网企业,如何做电子商城网站,网站后台为什么传不上图片今天只有两道题呢#xff0c;也很简单#xff0c;难度★吧#xff0c;能做出来。今天是有点懈怠了#xff0c;但是还是撑着做了两道题#xff0c;不是吗#xff0c;不要太苛责自己#xff0c;状态好的时候多写点#xff0c;状态差的时候少写点#xff0c;只要写了就不…今天只有两道题呢也很简单难度★吧能做出来。今天是有点懈怠了但是还是撑着做了两道题不是吗不要太苛责自己状态好的时候多写点状态差的时候少写点只要写了就不算原地踏步。一.两个数组的交集Ⅱ ★☆☆☆☆题目350. 两个数组的交集 II 给你两个整数数组nums1和nums2请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。我的思路这道题跟昨天的349. 两个数组的交集的区别是结果元素的次数不再局限为1次而是要符合交集的次数所以我用了相同的排序双指针的方法利用这个办法这道题看上去反而比昨天更简单了。只需要先排序然后在两个指针指向的元素相等时赋值到结果数组res中不相等时指向较小数的指针先后移动直到其中一个指针移动到数组末尾即可。代码class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); sort(nums1.begin(),nums1.end()); sort(nums2.begin(),nums2.end()); vectorint res; int p0; int q0; while(plen1 qlen2){ if(nums1[p]nums2[q]){ res.push_back(nums1[p]); p; q; }else if(nums1[p]nums2[q]){ p; }else{ q; } } return res; } };复杂度时间复杂度O(nlognmlogmnm)O(nlognmlogm)空间复杂度O(lognlogm)官方题解——哈希表利用哈希表的value记录对应的key的“次数”先循环数组1保存每个数字的出现次数然后遍历数组2的元素如果该元素在哈希表中则将其加入到结果数组中同时将对应的value减一表示已相等一次若再次相等一样的操作。然后遍历完数组2即可。代码class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { int len1nums1.size(); int len2nums2.size(); vectorint res; unordered_mapint,int map; for(int i0;ilen1;i){ map[nums1[i]]; } for(int i0;ilen2;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加一当sign3时temp记录的就是第三大的数值赋值给res。因为不满足第三大的情况都是输出最大值所以给res初始化为最大值没有满足的情况就直接输出最大值。代码class Solution { public: int thirdMax(vectorint nums) { //排序 //用标记值记录数值慢慢向后移动找到第三大的数即可反之输出最后一个数 int lennums.size(); sort(nums.begin(),nums.end()); int tempnums[len-1]; int sign1; int resnums[len-1]; for(int ilen-1;i0;i--){ if(nums[i]temp){ tempnums[i]; sign; } if(sign3){ restemp; break; } } return res; } };复杂度时间复杂度O(n)。遍历数组最坏的情况为n次所以时间复杂度为O(n)。空间复杂度O(1)。因为没有数组、哈希表这类的变量只有普通变量所以空间复杂度是常数。官方题解思路1——有序集合创建有序集合set利用其自动排序的特性存储前三大的元素需要保证set长度一直3如果加入了某元素set3则要删去最小的元素。最后若set3返回set中最小的值反之返回最大的值。代码class Solution { public: int thirdMax(vectorint nums) { setint 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代码1class Solution { public: int thirdMax(vectorint nums) { //用a、b、c模拟前三大元素 long aLONG_MIN,bLONG_MIN,cLONG_MIN; for(long num:nums){ //大于最大数 if(numa){ cb; ba; anum; }//在第一大和第二大之间 else if(anum numb){ cb; bnum; } //在第二大和第三大之间 else if(bnum numc){ cnum; } } return cLONG_MIN?a:c; } };代码2第二种写法利用指针a、b、c初始化为空表示无穷小然后在判断范围时加上指针是否为空的判断class Solution { public: int thirdMax(vectorint nums) { int *a nullptr, *b nullptr, *c nullptr; for (int num : nums) { if (a nullptr || num *a) { c b; b a; a num; } else if (*a num (b nullptr || num *b)) { c b; b num; } else if (b ! nullptr *b num (c nullptr || num *c)) { c num; } } return c nullptr ? *a : *c; } };复杂度时间复杂度O(n)空间复杂度O(1)