347. 前 K 個高頻元素(中等)

347. 前 K 個高頻元素

  • 1. 題目描述
  • 2.詳細題解
  • 3.代碼實現
    • 3.1 Python
    • 3.2 Java

1. 題目描述

題目中轉:347. 前 K 個高頻元素

在這里插入圖片描述

2.詳細題解

? ? 尋找出現頻率前 k k k高的元素,因此需要先統計各個元素出現的次數,該步驟時間復雜度為 O ( n ) O(n) O(n),再對各元素的出現頻率進行排序,假定不同元素的個數為 m m m,該步驟的最佳時間復雜度為 O ( m l o g ( m ) ) O(mlog(m)) O(mlog(m)),如歸并、堆排序等算法。
??這里介紹一種桶排序算法:桶排序(Bucket Sort)是一種排序算法,它通過將數據分散到有限數量的桶中,然后對每個桶中的數據單獨進行排序,最后按照順序將各個桶中的數據合并起來得到最終排序結果。簡單的說,已知數據種類有限,逐一遍歷數據并裝入相應的桶中,僅需 O ( n ) O(n) O(n)時間復雜度即可完成數據排序。
??對于本題,先統計各元素出現的頻率,再以元素的頻率作為桶,將相應頻率的元素放入指定桶中。具體算法如下:

  • Step1:初始化:統計各元素出現的頻率,數據結構為字典,算法時間復雜度為 O ( n ) O(n) O(n)
  • Step2:數組中元素個數為 n n n,構建 n + 1 n+1 n+1個桶,數據結構為數組,數組的索引下標對應元素出現的頻率(可進一步優化,桶的數據為元素出現的最大頻率);
  • Step3:遍歷各元素出現的頻率,放入對應桶中,算法時間復雜度為 O ( m ) O(m) O(m)
  • Step4:從右至左遍歷桶,如果桶中有元素,則放入最終結果:
  • Step5:當結果數量為 k k k時,程序結束;
  • Step8:返回結果。

3.代碼實現

3.1 Python

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:fre_dict = {}for num in nums:fre_dict[num] = fre_dict.get(num, 0) + 1res = [[] for _ in range(len(nums) + 1)]for key, value in fre_dict.items():res[value].append(key)ans = []for i in range(len(nums), 0, -1):if len(res[i]) > 0:ans.extend(res[i])if len(ans) == k:breakreturn ans

在這里插入圖片描述

3.2 Java

class Solution {public int[] topKFrequent(int[] nums, int k) {int[] res = new int[k];HashMap<Integer, Integer> fre_dict = new HashMap();for (int num: nums){if (fre_dict.containsKey(num)){fre_dict.put(num, fre_dict.get(num)+1);}else {fre_dict.put(num, 1);}}List<Integer>[] list = new List[nums.length+1];for(int key : fre_dict.keySet()){// 獲取出現的次數作為下標int i = fre_dict.get(key);if(list[i] == null){list[i] = new ArrayList();} list[i].add(key);}for (int i=list.length-1, j = 0; i>=0 && j < k; i--){if (list[i] == null) continue;for (int value: list[i]){res[j++] = value;}}return res;}
}

在這里插入圖片描述

??執行用時不必過于糾結,對比可以發現,對于python和java完全相同的編寫,java的時間一般是優于python的;至于編寫的代碼的執行用時擊敗多少對手,執行用時和網絡環境、當前提交代碼人數等均有關系,可以嘗試完全相同的代碼多次執行用時也不是完全相同,只要確保自己代碼的算法時間復雜度滿足相應要求即可,也可以通過點擊分布圖查看其它coder的code。

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

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

相關文章

柔性接觸力學及其建模仿真方法

柔性接觸力學是研究柔性體&#xff08;如柔性機器人、柔性結構等&#xff09;在接觸過程中產生的力學效應和相互作用的學科。它涉及到接觸力的計算、接觸變形的分析以及接觸過程中的能量轉換等多個方面。由于柔性體具有變形能力&#xff0c;其接觸過程往往比剛性體接觸更為復雜…

Transformer學習過程中常見的問題與解決方案 - Transformer教程

在機器學習領域&#xff0c;Transformer模型已經成為了處理自然語言處理&#xff08;NLP&#xff09;任務的主流工具。然而&#xff0c;在學習和使用Transformer的過程中&#xff0c;很多人會遇到各種各樣的問題。今天我們就來聊一聊Transformer學習過程中常見的問題以及對應的…

C++模板總結

文章目錄 寫在前面1. 函數模板1.1 函數模板的概念1.2 函數模板的原理1.3 函數模板的實例化1.4 函數模板的實例化模板參數的匹配原則 2. 類模板3. 非類型模板參數4. 模板的特化4.1 概念4.2 函數模板特化4.3 類模板特化 5. 模板分離編譯6. 總結 寫在前面 進入C以后&#xff0c;C…

智能小車——初步想法

需要參考輪趣的智能小車自己搭建一臺智能機器人&#xff0c;這里從底層控制開始逐步搭建。 控制模式 之后要自行搭建智能小車&#xff0c;所以將輪趣的底盤代碼進行學習&#xff0c;根據開發手冊先大致過一遍需要的內容。 有做很多個控制方法&#xff0c;包括了手柄、串口、…

MySQL中的JOIN、LEFT JOIN、RIGHT JOIN講解

在 MySQL 中&#xff0c;JOIN 是一種非常強大的功能&#xff0c;它允許你將兩個或多個表中的行結合起來&#xff0c;基于兩個表之間的共同字段。這種操作在數據庫查詢中非常常見&#xff0c;特別是在處理關系型數據庫時。下面我將分別解釋 JOIN、LEFT JOIN&#xff08;也稱為 L…

uin-app微信小程序自定義tabBar底部菜單實現簡單示例(工作筆記)

在微信小程序中實現自定義 tabBar 可以為你的應用提供更加靈活和個性化的底部導航菜單。由于微信小程序的官方 tabBar 配置功能有限&#xff0c;自定義 tabBar 成為了很多開發者實現復雜底部導航的選擇。以下是一個簡單的示例&#xff0c;說明如何在小程序中實現自定義 tabBar。…

Linux下常見壓縮文件tar.xz、tar.bz2、tar.gz的區別和詳解

文章目錄 tar.xz tar.bz2 tar.gz 的區別三種文件的解壓方式tar.xz的解壓三種壓縮文件的創建方式 tar.xz tar.bz2 tar.gz 的區別 這三個文件擴展名都表示壓縮后的檔案文件&#xff0c;但它們使用不同的壓縮算法。 tar.xz: tar 代表 Tape Archive&#xff0c;它是一種將多個文件…

House holder reflections and Givens rotations

House holder reflections and Givens rotations Householder反射和Givens旋轉是兩種常見的線性代數方法&#xff0c;用于將一個矩陣分解為正交矩陣(Q)和上三角矩陣&#xff0c;即QR分解。它們在數值線性代數中非常重要&#xff0c;特別是在求解線性方程組和特征值問題中。以下…

【若依管理系統】注意事項

1.前端字段必填 rules: {sceneName: [{ required: true, message: "場景名稱不能為空", trigger: "blur" }],orderNum: [{ required: true, message: "顯示排序不能為空", trigger: "blur" }], }, 2.IDEA&#xff0c;默認以debug模式…

python | pyvips,一個神奇的 Python 庫

本文來源公眾號“python”&#xff0c;僅用于學術分享&#xff0c;侵權刪&#xff0c;干貨滿滿。 原文鏈接&#xff1a;pyvips&#xff0c;一個神奇的 Python 庫&#xff01; 大家好&#xff0c;今天為大家分享一個神奇的 Python 庫 - pyvips。 Github地址&#xff1a;https…

Agents 要點

一、Agents概念 人類是這個星球上最強大的 Agent。Agent是一個能感知并自主地采取行動的實體&#xff0c;這里的自主性極其關鍵&#xff0c;Agent要能夠實現設定的目標&#xff0c;其中包括具備學習和獲取知識的能力以提高自身性能。 關鍵點&#xff1a;感知環境、自主決策、具…

前端項目筆記經驗-001

做項目有一段時間了&#xff0c;利用下班或者零碎時間的功夫&#xff0c;想分享一些個人心得和感受。與君共勉。 前端應該具備的幾個能力&#xff1a; &#xff08;1&#xff09;準備假數據&#xff08;模擬數據&#xff09;的能力&#xff0c;因為后端有時候接口沒有準備好&…

element plus 實現跨頁面+跨tab欄多選

文章目錄 element plus 層面數據層面 菜鳥好久沒寫博客了&#xff0c;主要是沒遇見什么很難的問題&#xff0c;今天碰見了一個沒有思路的問題&#xff0c;解決后立馬來和大家伙分享了&#xff01; 菜鳥今天要實現一個需求&#xff0c;就是&#xff1a;實現跨頁面跨 tab欄 多選…

力學篤行(四)Qt 線程與信號槽

線程與信號槽 1. 主窗口&#xff08;MainWindow&#xff09;主線程2. 線程2.1 QThread2.2 QtConcurrent::run()2.3 thread 的調用方式 3. 信號槽3.1 connect3.2 元對象系統中注冊自定義數據類型 附錄一 信號槽機制與主線程進行通信示例 1. 主窗口&#xff08;MainWindow&#x…

MySQL聯合索引最左匹配原則

MySQL中的聯合索引(也叫組合索引)遵循最左匹配原則&#xff0c;即在創建聯合索引時&#xff0c;查詢條件必須從索引的最左邊開始&#xff0c;否則索引不會被使用。在聯合索引的情況下&#xff0c;數據是按照索引第一列排序&#xff0c;第一列數據相同時才會按照第二列排序。 例…

CVE-2024-27292:Docassemble任意文件讀取漏洞復現 [附POC]

文章目錄 CVE-2024-27292&#xff1a;Docassemble任意文件讀取漏洞復現 [附POC]0x01 前言0x02 漏洞描述0x03 影響版本0x04 漏洞環境0x05 漏洞復現1.訪問漏洞環境2.構造POC3.復現 0x06 修復建議 CVE-2024-27292&#xff1a;Docassemble任意文件讀取漏洞復現 [附POC] 0x01 前言 …

冒泡排序與其C語言通用連續類型排序代碼

冒泡排序與其C語言通用連續類型排序代碼 冒泡排序冒泡排序為交換排序的一種&#xff1a;動圖展示&#xff1a;冒泡排序的特性總結&#xff1a;冒泡排序排整型數據參考代碼&#xff08;VS2022C語言環境&#xff09;&#xff1a; 冒泡排序C語言通用連續類型排序代碼對比較的方式更…

法律行業守護神:知識庫+AI大模型,解鎖企業知識全周期管理

在法律行業中&#xff0c;搭建一個有效的知識庫并進行企業知識全生命周期管理確實是一項不小的挑戰。法律環境的復雜性和不斷變化的法規要求企業必須持續更新和維護其知識庫&#xff0c;以確保所有信息的準確性和實時性。 這種系統化的信息管理不僅有助于提高律師和法律顧問的…

打卡第9天-----字符串

我在自學的時候,看了卡爾的算法公開課了,有些題目我就照葫蘆畫瓢寫了一遍js代碼,差不多都寫出來了,有暴力解法,有卡爾推薦的思路和方法。話不多說,直接上題上代碼吧: 一、翻轉字符串里的單詞 leetcode題目鏈接:151. 反轉字符串中的單詞 題目描述: 給你一個字符串 s…

5個自動化面試題,助你過關斬將!

面試時&#xff0c;自動化是軟件測試高頻面試內容&#xff0c;通過學習和準備面試題&#xff0c;你會對可能遇到的問題有所準備&#xff0c;從而減輕面試時的緊張感&#xff0c;讓你在面試中穩操勝券&#xff01; 今天&#xff0c;分享一些在面試中可能會遇到的自動化測試面試…