云南省中国建设工程造价管理协会网站,网站制作天津,自媒体怎么申请注册,北京网站上排名两个数组的交集 难度 简单 题目链接
这道题的难度不大#xff0c;我们可以把数组里的数据存到set里面。这样就完成了排序和去重#xff0c;然后我们再把一个set里面的数据和另外一个set数据进行比较。如果相同就插入到数组里。
代码如下#xff1a; 但是这个算法的时间复…
两个数组的交集 难度 简单 题目链接
这道题的难度不大我们可以把数组里的数据存到set里面。这样就完成了排序和去重然后我们再把一个set里面的数据和另外一个set数据进行比较。如果相同就插入到数组里。
代码如下 但是这个算法的时间复杂度为O(N*logN)我们有什么办法改进一下呢 两个数组里面的元素相比较小的相等就是交集然后同时。
大致思路 根据上面的思路12那么it2。 23it1。 此时it1和it2相等那么就同时当某一个数组结束交集就找完了。
代码如下 这个时间复杂度是O(N)。如果我们想求差集方法是相比较小的就是差集然后小的。如果相等了就同时。
前K个高频单词 难度 中等 题目链接
方法一
首先我们把words里面的单词个数统计一下 因为map里面是按照key(string)排序但我们需要按照次数排序。 但在标准库里面sort 要传随机迭代器map是双向迭代器所以不能直接传。 这里数组迭代器解引用后是map迭代器迭代器不支持排序。所以我们需要写仿函数来让里面的迭代器按照次数来排序 但是还是存在一些问题因为题目上还要求了如果不同的单词有相同出现频率 按字典顺序排序。但是标准库里面sort是不稳定的 可能让某些小的单词放在前面。所以标准库里面还提供了稳定的排序stable_sort。最后我们再把前k个单词找出来就行了 其实如果我们不使用stable_sort我们可以在仿函数比较的时候加上一些条件 意思就是如果次数相同就比较它们的ASCII码。
方法二 方法二并不采用sort来排序而是采用multimap来排序。但是这里还不行因为multimap默认是升序而我们要降序的方式。
