Astd::priority_queueはstd::vectorデフォルトのコンテナとしてaを使用します（これを参照してください）。の最初の要素に基づいて並べ替えるにはstd::vector<pair<int, int>>、独自の比較関数を定義する必要があります（これを参照してください）。これが私が理解していることです。
ここで、次のコードは、kO（NlogK）の空でない配列で最も頻繁な要素を返します。
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
if(nums.empty())
return vector<int>();
unordered_map< int, int > hashMap;
for(int i=0; i<nums.size(); i++)
hashMap[nums[i]]++;
priority_queue< pair< int, int >> pq;
vector< int > result;
unordered_map< int, int >::iterator it=hashMap.begin();
for(it=hashMap.begin(); it!=hashMap.end(); it++) {
//the first one is frequency and the second one is the value
pq.push(make_pair(it->second, it->first));
//the peculiar implementation below is because we the code to be O(NlogK)
if(pq.size()>(hashMap.size()-k)) {
result.push_back(pq.top().second);
pq.pop();
}
}
return result;
}
};
このコードは正しく機能し、裁判官に受け入れられます-しかし、どのように？を基になるコンテナとしてstd::priority_queue使用するstd::vector<pair<int, int>>は、正しくソートされるように、カスタム比較関数を含める必要があります。それで、それはどのように機能しますか？
率直に言って、それはそうするように設計されているので機能します。
いくつかのこと：
std::priority_queueはstd::less<T>、Tオーバーライドが指定されていない場合のデフォルトのコンパレータとして、を使用します。ここで、は基になるシーケンス値タイプです。std::less<T>operator <2つのT引数に対して呼び出し、最適なものや利用可能なものに解決します。したがって、これがシーケンスタイプコンパレータの特別なオーバーライドなしで希望どおりに機能する場合はoperator <、std::pair<int,int>そのワイヤにこのすべてが一緒に存在することを意味する必要があります。
そして確かにあります。のドキュメントを確認するとstd::pair<T1,T2>、operator <これを効果的に行うオーバーロードがあることがわかります。
if (lhs.first < rhs.first)
return true;
else if (!(rhs.first < lhs.first))
return lhs.second < rhs.second
else
return false;
これがどのように機能するかについてのマインドプレイの例は、読者が考えることに任されています。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加