推 pandix: 跑到O(n^2)去了 05/23 04:03
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/top-k-frequent-elements/description/
: 347. Top K Frequent Elements
: 給你一個陣列 nums，找出出現次數最多次的前k個元素是哪些。
: Example 1:
: Input: nums = [1,1,1,2,2,3], k = 2
: Output: [1,2]
: Example 2:
: Input: nums = [1], k = 1
: Output: [1]
好久沒寫leetcode了，決定回來寫
之前遇到學校作業太多，就會不想寫leetcode，希望之後能堅持住
寫個C++的，記憶體在90%以上，但速度是10%以下QQ
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
for (int n : nums) {
int r = isInVector(n);
if (r == -1) {
vc.push_back(make_pair(n, 1));
}
else {
vc[r].second++;
}
}
sort(vc.begin(), vc.end(), [](pair<int, int> a, pair<int, int> b) {
return a.second > b.second;
});
vector<int> result;
for (int i = 0; i < k; i++) {
result.push_back(vc[i].first);
}
return result;
}
private:
int isInVector(int n) {
int count = -1;
for (auto p : vc) {
count++;
if (n == p.first)
return count;
}
return -1;
}
vector<pair<int, int>> vc;
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.246.249 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1684783727.A.13F.html