力扣347:前K個高頻元素

給你一個整數數組?nums?和一個整數?k?,請你返回其中出現頻率前?k?高的元素。你可以按?任意順序?返回答案。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2
輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1
輸出: [1]

題解:

一、思路:

1.我希望將nums中的元素按照它們的出現次數從大到小排序。這樣輸出排序后的前K個元素就好;

2.如何得知nums中每個元素出現的次數呢?使用map哈希表。unordered_map<int,int>,key為nums中的元素,value為該元素出現的次數;

3.如何排序呢?考慮使用頂堆。大頂堆還是小頂堆呢?應該使用小頂堆。小頂堆中只維護K個元素,當新來的元素比隊尾的元素還大時,彈出隊頭的元素,在隊尾放入新的元素;

4.最后輸出小頂堆中所有的key。

二、代碼實現:

1.創建哈希表:

unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;
}

說明:map[nums[i]]++這句會執行將key為nums[i]的value進行++操作。如果沒有nums[i]的key,則會先創建一個<nums[i],0>,再對value進行++操作;

2.創建小頂堆:

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;
for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();
}

說明:

(1)

priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;

以上代碼中:pair<int,int>為pri_que中的數據類型;vector<pair<int,int>>為pri_que的底層數據結構;mycompare為pri_que的比較器類。由于是小頂堆,mycompare比較器類定義如下:

class mycompare {
public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}
};

(2)

for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();
}

unordered_map<int,int>::iterator it = map.begin()意味創建迭代器it作為循環變量;

3.取出頂堆中所有的元素:

vector<int>result;
for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();
}
return result;

完成代碼:

class Solution {class mycompare {public:bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {return lhs.second > rhs.second;}};
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> map;for (int i = 0; i < nums.size(); i++) {map[nums[i]]++;}priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> pri_que;for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {pri_que.push(*it);if (pri_que.size > k) pri_que.pop();}vector<int>result;for (int i = k - 1; i >= 0; i--) {result.push_back(pri_que.top().first);pri_que.pop();}return result;}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/web/77251.shtml
繁體地址,請注明出處:http://hk.pswp.cn/web/77251.shtml
英文地址,請注明出處:http://en.pswp.cn/web/77251.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

前饋神經網絡層

FeedForward Network 論文地址 https://arxiv.org/pdf/1706.03762 前饋網絡介紹 前饋網絡是Transformer模型中的關鍵組件&#xff0c;每個Transformer層包含一個多頭注意力模塊和一個前饋網絡模塊。該模塊通過兩次線性變換和激活函數&#xff0c;為模型提供非線性建模能力。其核…

如何將 sNp 文件導入并繪制到 AEDT (HFSS)

導入 sNp 文件 打開您的項目&#xff0c;右鍵單擊 “Result” 繪制結果 導入后&#xff0c;用戶可以選擇它進行打印。請參閱下面的示例。要點&#xff1a;確保從 Solution 中選擇它。

es-核心儲存原理介紹

原始數據 idusernamegradedescription1ahua87i like study2xiaowang92i like es3zhaoyun63i like java 倒排索引 description使用的text分詞&#xff0c;使用倒排索引 termidi1,2,3like1,2,3study1es2java3 分詞后&#xff0c;如果匹配 es&#xff0c;則需要逐行匹配&…

jmeter中監控服務器ServerAgent

插件下載&#xff1a; 將ServerAgent上傳至需要監控的服務器&#xff0c;mac/liunx啟動startAgent.sh&#xff08;啟動命令&#xff1a;./startAgent.sh&#xff09; 在jmeter中添加permon監控組件 配置需要監控的服務器IP地址&#xff0c;添加需要監控的資源 注意&#xf…

UML 狀態圖:以共享汽車系統狀態圖為例

目錄 一、初識 UML 狀態圖 二、共享汽車系統狀態圖詳解 &#xff08;一&#xff09;初始狀態與車輛空閑狀態 &#xff08;二&#xff09;用戶預定相關狀態 &#xff08;三&#xff09;等待取車與用戶取車狀態 &#xff08;四&#xff09;用戶還車及后續狀態 三、狀態圖繪…

橙子果品分級-目標檢測數據集(包括VOC格式、YOLO格式)

橙子果品分級-目標檢測數據集&#xff08;包括VOC格式、YOLO格式&#xff09; 數據集&#xff1a; 鏈接&#xff1a;https://pan.baidu.com/s/1jpdrylu06mm0r9pGVyb-AQ?pwd94a6 提取碼: 94a6 數據集信息介紹&#xff1a; 共有 9195 張圖像和一一對應的標注文件 標注文件格式…

uniapp 仿企微左邊公司切換頁

示例代碼&#xff1a; <template><view class"container"><!-- 遮罩層 --><view class"mask" v-if"showSidebar" click"closeSidebar"></view><!-- 側邊欄 --><view class"sidebar"…

pyqt中以鼠標所在位置為錨點縮放圖片

在編寫涉及到圖片縮放的pyqt程序時&#xff0c;如果以鼠標為錨點縮放圖片&#xff0c;圖片上處于鼠標所在位置的點&#xff08;通常也是用戶關注的圖片上的點&#xff09;不會移動&#xff0c;更不會消失在圖片顯示區域之外&#xff0c;可以提高用戶體驗&#xff0c;是一個值得…

巧記英語四級單詞 Unit5-中【曉艷老師版】

ignore v.無視&#xff0c;不理睬 發音“一個鬧”&#xff0c;對付一個無理取鬧的孩子&#xff0c;最好的方式就是無視 不理睬ignorant a.無知的&#xff0c;不禮貌的 對于什么事都無視&#xff0c;中國第一個不平等條約問也不知道就是無知的neglect n.忽視 negative消極的&a…

go 編譯的 windows 進程(exe)以管理員權限啟動(UAC)

引言 windows 系統&#xff0c;在打開某些 exe 的時候&#xff0c;會彈出“用戶賬戶控制(UAC)”的彈窗 “你要允許來自xx發布者的此應用對你的設備進行更改嗎&#xff1f;” UAC&#xff08;User Account Control&#xff0c;用戶賬戶控制&#xff09;是 Windows 操作系統中的…

go.mod介紹

在 Go 項目中&#xff0c;.mod 文件&#xff08;全稱 go.mod&#xff09;是 Go 語言模塊&#xff08;Module&#xff09;系統的核心配置文件&#xff0c;用于定義和管理項目的依賴關系、模塊名稱及兼容性規則。以下是其核心作用與結構的詳細說明&#xff1a; 一、go.mod 文件的…

基于CATIA參數化管道建模的自動化插件開發實踐——NX建模之管道命令的參考與移植

引言 在機械設計領域&#xff0c;CATIA作為行業領先的CAD軟件&#xff0c;其強大的參數化建模能力備受青睞。本文介紹如何利用Python的PySide6框架與CATIA二次開發技術&#xff0c;開發一款智能管狀體生成工具。該工具借鑒了同類工業軟件NX的建模的管道命令&#xff0c;通過Py…

centos7使用yum快速安裝最新版本Jenkins-2.462.3

Jenkins支持多種安裝方式&#xff1a;yum安裝、war包安裝、Docker安裝等。 官方下載地址&#xff1a;https://www.jenkins.io/zh/download 本次實驗使用yum方式安裝Jenkins LTS長期支持版&#xff0c;版本為 2.462.3。 一、Jenkins基礎環境的安裝與配置 1.1&#xff1a;基本…

BiliNote:開源的AI視頻筆記生成工具,讓知識提取與分享更高效——跨平臺自動生成結構化筆記,實現從視頻到Markdown的智能轉化

引言:視頻學習的痛點與BiliNote的解決方案 隨著知識視頻化趨勢的加速,B站、YouTube等平臺成為學習與信息獲取的重要渠道,但手動記錄筆記耗時低效、信息碎片化等問題依然突出。BiliNote的出現,通過AI驅動的自動化流程,將視頻內容轉化為結構清晰的Markdown筆記,支持截圖插…

DAX Studio將PowerBI與EXCEL連接

DAX Studio將PowerBI與EXCEL連接 具體步驟如下&#xff1a; 第一步&#xff1a;先打開一個PowerBI的文件&#xff0c;在外部工具欄里打開DAXStudio&#xff0c;如圖&#xff1a; 第二步&#xff1a;DAXStudio界面&#xff0c;點擊Advanced選項卡-->Analyze in Excel&#…

Redis-cli常用參數及功能的詳細說明

Redis-cli常用參數及功能的詳細說明 相關參考知識書籍 <<Redis運維與開發>> 以下是Redis-cli常用參數及功能的詳細說明 1. **-r?&#xff08;重復執行命令&#xff09;** 作用&#xff1a;重復執行指定命令多次。 示例&#xff1a;執行3次PING?命令&#xff1…

百度文心4.5 Turbo與DeepSeek、豆包、元寶對比:技術路徑與市場格局分析??

今日&#xff0c;百度發布文心大模型4.5 Turbo與X1 Turbo&#xff0c;主打多模態能力提升與成本優化&#xff0c;成為AI搜索領域的重要技術迭代。與此同時&#xff0c;DeepSeek、豆包&#xff08;字節跳動&#xff09;、騰訊元寶等競品憑借差異化定位持續搶占市場。本文將從技術…

施工配電箱巡檢二維碼應用

在過去&#xff0c;施工配電箱的巡檢主要依賴于紙質記錄方式。巡檢人員每次巡檢時&#xff0c;都要在紙質表格上詳細填寫配電箱的各項參數、運行狀況以及巡檢時間等信息。這種方式在實際操作中暴露出諸多嚴重問題&#xff0c;信息易出現錯誤、數據會有造假現象、數據量龐大整理…

國產AI大模型超深度橫評:技術參數全解、商業落地全場景拆解

評測方法論與指標體系 評測框架設計 采用三層評估體系&#xff0c;涵蓋技術性能、商業價值、社會效益三大維度&#xff0c;細分為12個二級指標、36個三級指標&#xff1a; 測試環境配置 項目配置詳情硬件平臺8NVIDIA H100集群&#xff0c;NVLink全互聯&#xff0c;3TB內存軟…

施工安全巡檢二維碼制作

進入新時代以來&#xff0c;人們對安全的重視程度越來越高。特別在建筑施工行業&#xff0c;安全不僅是關乎著工人的性命&#xff0c;更是承載著工人背后家庭的幸福生活。此時就誕生了安全巡檢的工作&#xff0c;而巡檢過程中內容龐雜&#xff0c;安全生產檢查、隱患排查、施工…