Leetcode 347:前k个高频元素
题目描述
给定一个非空的整数数组,返回其中出现频率前 k 高的元素。
说明:
你可以假设给定的 k 总是合理的,且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
示例
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
解题思路
一看到这种出现频率最高的k个数字这种题目,就会想到key-value pair,就自然想到map,然后就可以使用map来做。
所以我需要做的就是两步:第一步,将元素插入map中,元素值为key,出现次数为value。第二步,将map按照value进行降序排序。
由于我们没办法使用sort直接对map进行排序,这一点之前也说过,所以依旧是将其转换为一个vector,然后进行排序,只不过我这里使用lambda函数。
最后,将map前k项的key值push到result即可。
代码实现
vector<int> topKFrequent(vector<int>& nums, int k) { map<int, int> mymap; for (int i = 0; i < nums.size(); i++) { if (mymap.find(nums[i]) != mymap.end())//复杂度O(1) ++mymap[nums[i]]; else { mymap.insert(pair<int, int>(nums[i], 1)); } } vector<int>result; vector<pair<int, int>>mapsort(mymap.begin(), mymap.end()); sort(mapsort.begin(), mapsort.end(), [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second; }); int count = 0; for (auto it = mapsort.begin(); count < k; count++, ++it) { result.push_back(it->first); } return result;}
代码性能
插入性能:O(logn),n个元素为O(nlogn)
排序为O(nlogn)
总的来说,时间复杂度为O(nlogn)。
符合要求
执行用时有一些高,内存消耗尚可。
Leetcode 394 字符串解码
题目描述
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
示例
s = “3[a]2[bc]”, 返回 “aaabcbc”.
s = “3[a2]“, 返回 “accaccacc”.
s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.
解题思路
这个题其实之前在做某次笔试的时候遇到过更复杂的,但是这里简单多了。利用两个栈,一个栈num用来存放存储的数字,一个栈str用来存放字符串,当识别到[
的时候,将数字和前面以后的字母分别push进入两个栈,然后遇到]
的时候,pop出数字,这个数字就对应着str中最上面的字符串重复的次数。
代码实现
string decodeString(string s) { string result = ""; stack<int>nums; stack<string>str; int num = 0; int len = s.size(); for (int i = 0; i < len; i++) { if (s[i] >= '0' && s[i] <= '9') { num = num * 10 + s[i] - '0'; } else if ((s[i] >= 'a' && s[i] <= 'z')||(s[i]>='A'&&s[i]<='Z')) { result = result + s[i]; } else if (s[i] == '[')//将‘[’前的数字压入nums栈内, 字母字符串压入strs栈内 { nums.push(num); num = 0; str.push(result); result = ""; } else if (s[i] == ']') //遇到‘]’时,操作与之相配的‘[’之间的字符,使用分配律 { int times = nums.top(); nums.pop(); for (int j = 0; j < times; j++) { str.top() += result; //之后若还是字母,就会直接加到res之后,因为它们是同一级的运算 //若是左括号,res会被压入strs栈,作为上一层的运算 } result = str.top(); str.pop(); } } return result;}